题目链接：http://acm.hust.edu.cn/vjudge/contest/126362#problem/F
比赛的时候没有图，也没有看群消息，看到这题自己臆想出了一种走法。。。说明看题真的很重要，不要先入为主，主观臆测！！！！这题是一个数字三角形的问题，麻烦一点的是倒过来求，但弄清楚怎么走也很简单了。。感觉这个有点类似dijkstra 算法。。
#include#include #include #include #include #include using namespace std;#define N 250int d[N][N],a[N][N];int main(){ int t,n,m; int c=1; scanf("%d",&t); while(t--) { memset(d,0,sizeof(d)); memset(a,0,sizeof(a)); scanf("%d",&n); m=2*n-1; for(int i=1;i<=m;i++)//输入 { if(i<=n) { for(int j=1;j<=i;j++) scanf("%d",&d[i][j]); } else { for(int j=1;j<=(2*n-i);j++)//多写几个数 就找出规律了 scanf("%d",&d[i][j]); } } a[1][1]=d[1][1];//从d[1][1] 开始 for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) { if(j==1) a[i][j]=d[i][j]+a[i-1][j]; else if(j==i) a[i][j]=d[i][j]+a[i-1][j-1]; else a[i][j]=d[i][j]+max(a[i-1][j-1],a[i-1][j]); } for(int i=n+1;i<=m;i++) for(int j=1;j<=2*n-i;j++) a[i][j]=d[i][j]+max(a[i-1][j],a[i-1][j+1]); printf("Case %d: ",c); printf("%d\n",a[m][1]); c++; } return 0;}