POJ1163 The Triangle: 倒三角形问题

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 const int max_size=1001;
 7 int n, a[max_size][max_size];
 8 int f[3][max_size];
 9 void initiate(){
10     memset(a,-1,sizeof(a));
11     memset(f,0,sizeof(f));
12     for(int i=1;i<=n;i++){
13         for(int j=1;j<=i;j++){
14             scanf("%d",&a[i][j]);
15         }
16     }
17 }
18 void solve(){
19     int pt_row=n;
20     for(int column=1;column<=n;column++){
21         f[pt_row%2][column]=a[pt_row][column];
22     }
23     for(int row=n-1;row>=1;row--){
24         for(int pt_col=1;pt_col<=row;pt_col++){
25             f[(pt_row-1)%2][pt_col]=a[pt_row-1][pt_col]+max(
26                 f[pt_row%2][pt_col],
27                 f[pt_row%2][pt_col+1]
28             );
29         }
30         --pt_row;
31     }
32     printf("%d\n",f[pt_row%2][1]);
33 }
34 int main(){
35     while(scanf("%d",&n)!=EOF){
36         initiate();
37         solve();
38     }
39     return 0;
40 }