华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1361|回复: 3
打印 上一主题 下一主题

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

[复制链接]

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
跳转到指定楼层
楼主
发表于 2018-10-3 23:37:25 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
       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
回复

使用道具 举报

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
沙发
 楼主| 发表于 2018-10-3 23:38:02 | 只看该作者
  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. int main()
  8. {
  9.     ///freopen("triangle.in","r",stdin);
  10.     ///freopen("triangle.out","w",stdout);
  11.     cin>>n;
  12.     FOR(i,1,n)
  13.     {
  14.         FOR(j,1,i) cin>>a[j];
  15.         For(j,i,1) c[j]=a[j]+max(c[j],c[j-1]);
  16.     }
  17.     FOR(i,1,n) if(c[i]>ans) ans=c[i];
  18.     cout<<ans;
  19.     return 0;
  20. }
  21. /*
  22. 5
  23. 7
  24. 3 8
  25. 8 1 0
  26. 2 7 4 4
  27. 4 5 2 6 5
  28. */
复制代码
回复 支持 反对

使用道具 举报

9

主题

158

帖子

470

积分

华一学生

积分
470
QQ
板凳
发表于 2018-10-4 08:09:59 | 只看该作者
  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. }
复制代码
回复 支持 反对

使用道具 举报

2

主题

19

帖子

114

积分

注册会员

Rank: 2

积分
114
地板
发表于 2019-11-1 21:05:23 | 只看该作者
  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. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 15:12 , Processed in 0.102544 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表