首页 > 代码库 > BZOJ 1087状态压缩DP

BZOJ 1087状态压缩DP

  状态压缩DP真心不会写,参考了别人的写法。

先预处理出合理状态,

我们用二进制表示可以放棋子的状态,DP[I][J][K]:表示现在处理到第I行,J:表示第I行的状态,K表示现在为止一共放的棋子数量。

#include<stdio.h>#include<iostream>#define N 1111using namespace std;typedef long long ll;int num,n,m;ll dp[11][1<<11][90];int hh[N],hnum[N];int mp[1111][1111];int check(int x,int y){    if (x&(y<<1)) return 0;    if (x&(y>>1)) return 0;    if (x&y) return 0;    return 1;}int judge(int x){    if (x&(x<<1)) return 0;    if (x&(x>>1)) return 0;    return 1;}int getsum(int x){    int ans=0;    while (x)    {         if (x&1) ans++;         x>>=1;    }    return ans;}void pre(){    num=0;    for (int i=0;i<(1<<n);i++)       if (judge(i))    {       hh[++num]=i;       hnum[num]=getsum(i);    }    for (int i=1;i<=num;i++)         for (int j=1;j<=num;j++)          if (check(hh[i],hh[j]))     mp[i][j]=mp[j][i]=1;}int main(){    cin>>n>>m;    pre();    dp[0][1][0]=1;    for (int i=0;i<n;i++)        for (int j=1;j<=num;j++)          for (int k=0;k<=m;k++)            if (dp[i][j][k])        for (int p=1;p<=num;p++)              if (mp[j][p]&&k+hnum[p]<=m)    dp[i+1][p][k+hnum[p]]+=dp[i][j][k];    ll ans=0;    for (int i=1;i<=num;i++)        ans+=dp[n][i][m];    cout<<ans<<endl;    return 0;}