题目详见http://acm.hdu.edu.cn/showproblem.php?pid=2084
题目的意思就是从上到下,找到一个路径加起来和是最大的。 这个很简单,就是一个表达式的事,没什么可多想的。遍历是不现实的,也没必要。这个DP 很好想,是我做过最简单的DP了。 状态转移方程 array[i][j]+=MAX{array[i-1][j-1],array[i-1][j]} 不多说了,直接上代码
#include <iostream> using namespace std; int main() { int array[101][101]; int i,j; int C,N,Max; for(i=0;i<=100;i++) { for(j=0;j<=100;j++) array[i][j]=0; } cin>>C; while(C--) { cin>>N; for(i=1;i<=N;i++) { for(j=1;j<=i;j++) cin>>array[i][j]; } for(i=1;i<=N;i++) { for(j=1;j<=i;j++) { if(array[i-1][j-1]>=array[i-1][j]) array[i][j]+=array[i-1][j-1]; else array[i][j]+=array[i-1][j]; } } Max=0; for(i=1;i<=N;i++) if(array[N][i]>Max) Max=array[N][i]; cout<<Max<<endl; } return 0; }
转载请注明出处http://blog.csdn.net/liangbopirates/article/details/9709071