数字三角形，DP裸题
1 #include<stdio.h>
2 #include<string.h>
3 #define max(a,b) (a)>(b)?a:b
4
5 int g[101][101],dp[101][101];
6
7 int max1(int i,int j){
8 return i>j?i:j;
9 }
10
11 int main(){
12 int C;
13 while(scanf("%d",&C)!=EOF){
14 for(int q=1;q<=C;q++){
15 int N;
16 scanf("%d",&N);
17 memset(dp,0,sizeof(dp));
18 int i,j;
19 for(i=1;i<=N;i++){
20 for(j=1;j<=i;j++){
21 scanf("%d",&g[i][j]);
22 }
23 }
24 dp[1][1]=g[1][1];
25 for(i=2;i<=N;i++){
26 for(j=1;j<=i;j++){
27 if(j==1)dp[i][j]=dp[i-1][j]+g[i][j];
28 else if(j==i)dp[i][j]=dp[i-1][j-1]+g[i][j];
29 else dp[i][j]=max1(dp[i-1][j-1],dp[i-1][j])+g[i][j];
30 }
31 }
32 int m=dp[N][1];
33 for(i=2;i<=N;i++)if(dp[N][i]>m)m=dp[N][i];
34 printf("%d
",m);
35 }
36
37 }
38 return 0;
39 }