http://acm.hdu.edu.cn/showproblem.php?pid=2084简单的DP,用两种方法，一种是从下向上DP，另一种是从上向下DP，下面是自下向上的方法。
状态转换方程：D[j]=max(D[j]+P[i][j],D[j+1]+P[i][j])
#include <iostream>
#include <algorithm>
using namespace std;
int d[101],p[101][101];
int max(int a,int b)
{
return a>b? a:b;
}
int main()
{
int t,n,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&p[i][j]);
memset(d,0,sizeof(d));
for(i=1;i<=n;i++)
d[i]=p[n][i];
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
d[j]=max(d[j]+p[i][j],d[j+1]+p[i][j]);
printf("%d\n",d[1]);
}
return 0;
}posted on 2011-04-03 10:06
大大木马 阅读(286)
评论(0) 编辑 收藏 引用