华师一附中OI组

标题: P1216 [USACO1.5]数字三角形 Number Triangles [打印本页]
作者: universehyf    时间: 2018-10-3 23:37
标题: P1216 [USACO1.5]数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
       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    时间: 2018-10-3 23:38
  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;

  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. */
复制代码
作者: 黄煦喆    时间: 2018-10-4 08:09
  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. }
复制代码
作者: 秀木于林    时间: 2019-11-1 21:05
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2