这到题我是用压缩DP做的，但是要是n再大一些就不能这么做了。每一行取或不取分别用1、0来表示。那么我们可以用二进制来表示每行的状态。状态转移方程为：f[i][j]=max{f[i-1][k]+sum(i,j),k为第i-1行的一个状态，且j&k==0}，sum(i,j)表示第i行满足状态j的数之和。对于每行的状态不能连续出现两个或多个1，因此可以把这种状态舍去。最后用滚动数组。详细见代码：
#include<iostream>
using namespace std;
int n;
int map[21][21];
int dp[2][1<<20+1];
int s[1<<20+1];
int bit[21];
int main()
{
int i,j,k;
bit[1]=1;
for(i=1;i<n;i++) bit[i+1]=1<<i;
int top=0;
for(i=0;i<(1<<20);i++)
{
for(j=1;j<20;j++)
{
if((i&(1<<(j-1)))&&(i&(1<<j)))
break;
}
if(j==20) s[top++]=i;
}
while(scanf("%d",&n)!=EOF)
{
int ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
for(j=0;j<top;j++)
{
int temp=0;
if(s[j]>=(1<<n)) break;
for(k=1;k<=n;k++)
{
if(s[j]&(1<<(k-1)))
temp+=map[i][k];
}
int minn=0;
for(k=0;k<top;k++)
{
if(s[k]>=(1<<n)) break;
if((s[k]&s[j])==0)
{
if(minn<dp[(i-1)&1][k])
minn=dp[(i-1)&1][k];
}
}
dp[i&1][j]=minn+temp;
if(ans<dp[i&1][j]) ans=dp[i&1][j];
}
}
printf("%d\n",ans);
}
return 0;
}posted on 2010-08-12 21:08
wuxu 阅读(346)
评论(0) 编辑 收藏 引用 所属分类:
动态规划