#include <iostream>
using namespace std;
int map[351][351];
int dp[351][351];
int n;
int cmax(int a,int b)   {return a > b ? a : b;}
int d(int i,int j)
{
    if(dp[i][j] >= 0)   return dp[i][j];
    return dp[i][j] = map[i][j] + (i == n - 1 ? 0 : cmax(d(i + 1,j),d(i + 1,j + 1)));
}
int main()
{
    int i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i = 0,k = 1;i < n;i ++,k++)
            for(j = 0;j < k;j++)
                scanf("%d",&map[i][j]);
        memset(dp,-1,sizeof(dp));
        int ans = d(0,0);
        printf("%d\n",ans);
    }
    return 0;
}

• Re:记忆化搜索，贴代码~ (579) buptpanda 2012-02-01 23:50:28