转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1300454092
和POJ3176一模一样，不懂做这题的去看看我对3176的解释
这是地址
http://blog.csdn.net/lyy289065406/article/details/6648150
不骗人，确实是一模一样的代码O(∩_∩)O哈哈~
1 //Memory Time
2 //232K 0MS
3
4 #include<iostream>
5 using namespace std;
6
7 int max(int a,int b)
8 {
9 return a>b?a:b;
10 }
11
12 int main(int i,int j)
13 {
14 int n;
15 while(cin>>n)
16 {
17 int **way=new int*[n+1]; //动态申请二维数组的第一维，每个元素都是一个一维数组的指针
18
19 /*Input & Initial*/
20
21 for(i=0;i<=n;i++)
22 {
23 way[i]=new int[i+2]; //动态申请二维数组的第二维，每一行的空间
24 for(j=0;j<=i+1;j++)
25 way[i][j]=0; //不能用memset初始化
26
27 if(i!=0)
28 for(j=1;j<=i;j++)
29 cin>>way[i][j];
30 }
31
32 /*Dp*/
33
34 int max_weight=0;
35 for(i=1;i<=n;i++)
36 for(j=1;j<=i;j++)
37 {
38 way[i][j] += max(way[i-1][j-1],way[i-1][j]);
39
40 if(i==n && max_weight<way[i][j])
41 max_weight=way[i][j];
42 }
43
44 cout<<max_weight<<endl;
45
46 delete[] way;
47 }
48 return 0;
49 }