洛谷1896 [SCOI2005]互不侵犯

Luogu

算法

发现数据范围很小,果断状压。
发现是求方案数,果断DP。

设$f[i][j][k]$表示i行,放好了$j$个国王,第$i$行的放置状态为$k$的方案数。

首先预处理出所有状态,然后处理出第一行(边界)。
然后DP即可。详见代码。

代码

#include <bits/stdc++.h>
typedef int mainint;
#define int long long
#define re register
using namespace std;
int N,K,s=0;
int bit[1<<10],cnt[1<<10];
int f[10][100][1<<10]; //f[i][j][k]表示前i行,放好了j个国王,第i行的放置状态为k的方案数  
inline void Dfs(int p,int b,int c) { //预处理
    if (p>N) { bit[++s]=b; cnt[s]=c; }
    else { Dfs(p+2,b+(1<<p-1),c+1); Dfs(p+1,b,c); }
}
mainint main() {
    scanf("%lld%lld",&N,&K); Dfs(1,0,0);
    for (re int i=1;i<=s;i++) f[1][cnt[i]][bit[i]]=1;
    for (re int i=2;i<=N;i++)
        for (re int j=1;j<=s;j++) //这一行 
            for (re int k=1;k<=s;k++) { //上一行 
                if (bit[j]&bit[k]) continue;
                if ((bit[j]<<1)&bit[k]) continue;
                if (bit[j]&(bit[k]<<1)) continue;
                for (re int t=cnt[j];t<=K;t++)
                    f[i][t][bit[j]]+=f[i-1][t-cnt[j]][bit[k]];
            }
    int ans=0;
    for (re int i=1;i<=s;i++) ans+=f[N][K][bit[i]];
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 12 : 58 PM

发表评论