hdu1565 方格取数(1) (状压dp入门)

题目

题解

先预处理所有合法状态（不相邻的）

再预处理所有合法状态的sum值

然后枚举上一行向下一行的转移

其实自己的代码dp[i][state[j]]可以开成dp[i][j]以缩小空间，

毕竟是离散化过的j，

n=20的时候cnt=17710不知道是怎么O(n*cnt*cnt)过的……

代码

#include<iostream>
#include<cstdio>
#include<cmath> 
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
int n;
ll a[21][21];
ll state[1<<20],cnt;
ll res,dp[21][1<<20];
void init()
{
	cnt=res=0;
	for(int i=1;i<(1<<n);++i)
	{
		if(!(i&(i<<1)))state[cnt++]=i;
	}
} 
int main()
{
	while(~scanf("%d",&n))
	{
	init();
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<n;++j)
        scanf("%lld",&a[i][j]);
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<cnt;++j)
		{
			ll t=state[j],num=0;
			ll sum=0;
			for(;t;num++,t>>=1)
			if(t&1)sum+=a[i][num];
			dp[i][state[j]]=sum;
			//printf("%d:%lld:%lld\n",i,state[j],dp[i][state[j]]);
		}
		//puts("");
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<cnt;++j)//这行 
		{
			ll mx=0;
			for(int k=0;k<cnt;++k)//上行 
			{
				if(!(state[j]&state[k]))
				mx=max(dp[i-1][state[k]],mx);
			}
			dp[i][state[j]]+=mx;
			res=max(res,dp[i][state[j]]); 
		}
	}
	printf("%lld\n",res);
    }
	return 0;
}