P1216 [USACO1.5]数字三角形 Number Triangles

universehyf

题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
       7
     3  8
   8  1  0
  2  7  4  4
4  5  2  6  5
在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大值30

输入输出格式

输入格式：
第一个行包含 R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的整数是非负的且不大于100。

输出格式：
单独的一行,包含那个可能得到的最大的和。

输入样例#1：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例#1：
30

universehyf

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. #define FOR(iii,nn,mm) for(int iii=nn;iii<=mm;iii++)
   
5. #define For(iii,nn,mm) for(int iii=nn;iii>=mm;iii--)
   
6. int a[100000],c[100000],ans=0,n;
   
7. 
   
8. int main()
   
9. {
   
10.     ///freopen("triangle.in","r",stdin);
    
11.     ///freopen("triangle.out","w",stdout);
    
12.     cin>>n;
    
13.     FOR(i,1,n)
    
14.     {
    
15.         FOR(j,1,i) cin>>a[j];
    
16.         For(j,i,1) c[j]=a[j]+max(c[j],c[j-1]);
    
17.     }
    
18.     FOR(i,1,n) if(c[i]>ans) ans=c[i];
    
19.     cout<<ans;
    
20.     return 0;
    
21. }
    
22. /*
    
23. 5
    
24. 7
    
25. 3 8
    
26. 8 1 0
    
27. 2 7 4 4
    
28. 4 5 2 6 5
    
29. */

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int n;
   
4. int a[1001][1001];
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for(int i=1;i<=n;i++)
   
9.         for(int j=1;j<=i;j++)cin>>a[i][j];
   
10.     for(int i=n;i>1;--i)
    
11.         for(int j=1;j<=i;j++)
    
12.             a[i-1][j]+=max(a[i][j],a[i][j+1]);
    
13.     cout<<a[1][1];
    
14.     return 0;
    
15. }
    

复制代码

秀木于林

1. #include<iostream>
   
2. using namespace std;
   
3. int mp[1001][1001],dp[1001][1001]= {0},ans=0,n;
   
4. int main()
   
5. {
   
6.     ///dp[i][j]=max(dp[i−1][j],dp[i−1][j−1])+map[i][j];
   
7.     cin>>n;
   
8.     for(int i=1; i<=n; i++)
   
9.         for(int j=1; j<=i; j++)
   
10.             cin>>mp[i][j];
    
11.     for(int i=1; i<=n; i++)
    
12.         for(int j=1; j<=i; j++)
    
13.         {
    
14.             dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + mp[i][j];
    
15.             if(dp[i][j] > ans)
    
16.             {
    
17.                 ans = dp[i][j];
    
18.             }
    
19.         }
    
20.         cout<<ans;
    
21.     return 0;
    
22. }
    

复制代码