【輪廓線DP，狀壓DP】BZOJ1087 [SCOI2005]互不侵犯King

題面在這裡

輪廓線DP的經典題……

可以發現，對于目前點(i,j)，隻有前面n+1個格子與其有關（如下圖）

那麼這n+1個位置就是(i,j)的輪廓線。

把輪廓線上的狀态用位運算壓縮一下即可。

f[c][s][k] 表示位置c（滾動數組優化空間），輪廓線上狀态s，已經放了k個王的方案數

那麼顯然，若(i,j)不放王：

f[c][ss][k]+=f[c^1][s][k];
           

（ss是新輪廓線的狀态）

若(i,j)放王，就要讓(i-1,j-1)、(i-1,j)、(i-1,j+1)、(i,j-1)都沒有王：

if (k<K&&check(i,j,s)) f[c][ss+][k+]+=f[c^][s][k];
           

那麼就完成了

附上代碼：

#include<cstdio>
#include<cstring>
#define LL long long
const int maxs=,maxk=;
int n,K;
LL f[][maxs][maxk],ans=;
bool check(int i,int j,int s){
    if (i>&&j>&&(s&(<<n))) return ;
    if (i>&&(s&(<<n-))) return ;
    if (i>&&j<n&&(s&(<<n-))) return ;
    if (j>&&(s&)) return ;
    return ;
}
int main(){
    scanf("%d%d",&n,&K);
    int c=;f[][][]=;
    for (int i=;i<=n;i++)
     for (int j=;j<=n;j++){
        c^=;memset(f[c],,sizeof(f[c]));
        for (int s=;s<(<<n+);s++){
            int ss=(s<<)%(<<n+);
            for (int k=;k<=K;k++){
                f[c][ss][k]+=f[c^][s][k];
                if (k<K&&check(i,j,s)) f[c][ss+][k+]+=f[c^][s][k];
            }
        }
     }
    for (int s=;s<(<<n+);s++) ans+=f[c][s][K];
    printf("%lld",ans);
    return ;
}