IOI94

<问题分析>

从下向上分析每个状态s[i][j]代表从底部到这个位置的最大值，状态转移方程 s[i][j]=max{s[i+1][j],s[i+1][j+1]}+w[i][j]

 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     int i,j,k,n;
 6     char v[1001][1001];
 7     long s[2][1001];
 8     scanf("%d",&n);
 9     for(i=1;i<=n;i++)
10     {
11         for(j=1;j<=i;j++)
12         scanf("%d",&v[i][j]);
13     }
14     for(i=1;i<=n;i++)
15       s[n%2][i]=v[n][i];
16     for(i=n-1;i>=1;i--)
17     {
18        for(j=1;j<=i;j++)
19        {
20           if(s[(i+1)%2][j]>s[(i+1)%2][j+1])
21             s[i%2][j]=s[(i+1)%2][j]+v[i][j];
22           else
23             s[i%2][j]=s[(i+1)%2][j+1]+v[i][j];
24        }
25     }
26     printf("%ld
",s[1][1]);
27     while(true);
28     return 0;
29 }