Luogu P1896 [SCOI2005]互不侵犯

YorkWu

May 28, 2019

1152 views

No comments

510 words

OI 题目

我感觉这道题还不错，状压dp的一类典型问题？ [题目链接](https://www.luogu.org/problemnew/show/P1896 "题目链接")

* * *

就是给个n*n的表格，然后放k个旗子，旗子每个旗子相邻的8个格子不能放旗子。问最多有几种放的方法。 状态就是$f\[i\]\[j\]\[k\]$表示第i行，状态为j，并且已经放了k个格子的方案总数。然后预处理一下can数组，保存左右互不侵犯的状态。再预处理$gs\[i\]$数组表示状态为i的有多少个旗子(i的二进制里有多少个1)。 这样枚举上一行状态，如果上一行和这一行满足左上，上，右上互不侵犯，那么$f\[i\]\[j\]\[k+gs\[i\]\]+=f\[i-1\]\[l\]\[k\]$ 最终答案就是所有$f\[n\]\[i\]\[k\]$的和。
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int n,k;
    ll f[10][1<<10][90],can[1<<10],tot;
    int gs[1<<10];
    
    int gs1(int x){
        int cnt=0;
        while(x){
            if(1&x) cnt++;
            x>>=1;
        }
        return gs[tot]=cnt;
    }
    
    int main(){
        cin>>n>>k;
        for(int i=0;i<(1<<n);i++) if(!(i&(i<<1))) can[++tot]=i,f[1][tot][gs1(i)]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=tot;j++){
                int a=can[j];
                for(int l=1;l<=tot;l++){
                    int b=can[l];
                    if(a&b) continue;
                    if(a&(b<<1)) continue;
                    if(a&(b>>1)) continue;
                    for(int g=0;g+gs[j]<=k;g++) f[i][j][gs[j]+g]+=f[i-1][l][g];
                }
            }
        }
        ll ans=0;
        for(int i=1;i<=tot;i++) ans+=f[n][i][k];
        cout<<ans;
        return 0;
    }
```

Last modification：March 14, 2020