pku + 1163

 

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     //freopen( "in.txt","r",stdin );
 8     int s1[100][100];
 9     int n;
10     scanf ( "%d",&n );
11     for ( int i = 0; i != n; ++i )
12         for ( int j = 0; j <= i; ++j )
13             scanf ( "%d",&s1[i][j] );
14     int max1[100];
15     for ( int i = 0; i != n; ++i )
16         max1[i] = s1[n-1][i];
17     //for ( int i = 0; i != n; ++i )
18     //    printf ( "%d ",max[i] );
19     for ( int i = n - 2;i >= 0--i  )
20     {
21         int sum1 = 0;
22         int sum2 = 0;
23         int k = 0;
24         for ( int j = 0; j != i+1++j )
25         {
26             sum1 = s1[i][j] + max1[k];
27             sum2 = s1[i][j] + max1[k+1];
28             max1[k] = max( sum1,sum2 );
29             ++k;
30         }
31     }
32     printf ( "%d\n",max1[0] );
33 }

posted on 2010-03-23 22:17 haozi 阅读(118) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜