DP方程：map[i][j]=map[i][j]+max(map[i+1][j],map[i+1][j+1]);
#include<iostream> #include<stdio.h> #include<string.h> #include<string> using namespace std; int C,N; int map[105][105]; void DP() { for(int i=N-1;i>=1;--i) for(int j=1;j<=i;++j) map[i][j]+=max(map[i+1][j],map[i+1][j+1]); } int main() { scanf("%d",&C); while(C--) { scanf("%d",&N); memset(map,0,sizeof(map)); //录入数据 for(int i=1;i<=N;++i) for(int j=1;j<=i;++j) scanf("%d",&map[i][j]); DP(); printf("%d/n",map[1][1]); } return 0; }
