Posted on 2011-10-03 12:16
acpeng 阅读(424)
评论(0) 编辑 收藏 引用 所属分类:
ACM程序
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2084
经典入门级DP，自底向上，层层递进。（所谓的记忆化搜索）
#include<stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
int a[103][103];
int main()
{
int t,n,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
scanf("%d",&a[i][j]);
for(i=n-1;i>0;i--)
for(j=0;j<i;j++)
a[i-1][j]+=max(a[i][j],a[i][j+1]);
printf("%d\n",a[0][0]);
}
return 0;
}