判斷存在性的動態規劃，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 閱讀(679)
評論(2) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃