lightoj 1004

很水的一个dp

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100;
int a[2*N+5][N+5],dp[2*N+5][N+5];
int main()
{
int T,n,i,j,ca=0;
cin>>T;
while(T--)
{
cin>>n;
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
for( i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin>>a[i][j];
for(i=n+1;i<=2*n-1;i++)
for(j=1;j<=2*n-i;j++)
cin>>a[i][j];
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=2*n-i;j++)
dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+a[i][j];
}
ca++;
cout<<"Case "<<ca<<": "<<dp[2*n-1][1]<<endl;
}
return 0;
}
上一篇:ASP.Net MVC开发基础学习笔记(4):校验、AJAX与过滤器


下一篇:Spring In Action(第三版)读书笔记