这道题是状压第2题,刚开始的想法还是naive了点,想要拿整个棋盘作为状态。
仔细分析就会发现,存整个棋盘的做法有大量的空间浪费,
因为一颗棋子的状态只由4个格子决定,转移时存整个棋盘实在是太亏了。
为了方便我们转移,用一行上的棋子情况来做状态,只用判断这一行是否合法和是否与上一行的状态冲突就行了。
这一行是否合法可以先预处理出来,并同时处理这一行有多少个棋子。
dp[现在第几行][这一行的状态][到目前为止有多少棋子]
其实最难的地方在于棋子个数的限制,但我打到一半看的题解所以没有仔细想= =
DP之路,长而难行。
代码:
#include<bits/stdc++.h> using namespace std ; long long dp[20][2000][100]; int n,m,can[2000],csz,MAX,num[2000]; long long ans; int getsum(int x){ int ret=0; while(x){ ret+=(x&1); x>>=1; } return num[csz]=ret; } void DP(){ int MAX = (1<<n)-1; for(int i=0;i<=MAX;i++){ if(!(i&(i<<1))) can[++csz]=i,dp[1][csz][getsum(i)]=1; } for(int i=2;i<=n;i++){ for(int j=1;j<=csz;j++){ int x=can[j]; for(int k=1;k<=csz;k++){ int y=can[k]; if((x&y) || (x&(y<<1)) || (x&(y>>1))) continue; for(int l=0;l+num[j]<=m;l++){ dp[i][j][num[j]+l] += dp[i-1][k][l]; } } } } for(int i=1;i<=csz;i++){ ans+=dp[n][i][m]; } return; } int main(){ cin>>n>>m; DP(); cout<<ans<<endl; return 0; }
TAG:SIN_XIII⑨