判断存在性的动态规划，d[i,j,k]==true表示存在着一条到达点（i，j）的路径，路径之和mod 100的结果为k。
以下是我的代码：
#include<iostream>
#include<string.h>
#define maxn 27
#define maxm 100
using namespace std;
long n,ans,r[maxn][maxn];
bool d[maxn][maxn][maxm];
int main()
{
cin>>n;
for(long i=1;i<=n;i++)
for(long j=1;j<=i;j++)
cin>>r[i][j];
// Input
memset(d,false,sizeof(d));
d[1][1][r[1][1]%maxm]=true;
// Init
for(long i=2;i<=n;i++)
for(long j=1;j<=i;j++)
for(long k=0;k<maxm;k++)
if(d[i-1][j][k])
d[i][j][(k+r[i][j])%maxm]=true;
else if(j>=2&&d[i-1][j-1][k])
d[i][j][(k+r[i][j])%maxm]=true;
// DP
ans=0;
for(long i=1;i<=n;i++)
for(long j=maxm-1;j>=0;j--)
if(d[n][i][j]&&ans<j)
ans=j;
cout<<ans<<endl;
// Output
return 0;
}
posted on 2010-10-29 22:50
lee1r 阅读(643)
评论(2) 编辑 收藏 引用 所属分类:
题目分类：动态规划