Posted on 2011-10-03 12:16
acpeng 閱讀(435)
評論(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;
}