【题解】洛谷P1896 [SCOI2005] 互不侵犯（状压DP）

洛谷P1896：https://www.luogu.org/problemnew/show/P1896

前言

这是一道状压DP的经典题 

原来已经做过了 但是快要NOIP 复习一波

关于一些位运算的知识点参考：

https://blog.csdn.net/fox64194167/article/details/20692645

思路

看数据识算法系列

我们用f[i][j][k]来表示第i行为状态j 并且前i行已经放了k个国王

对于状态我们可以先预处理出来

因为每个格子有放和不放两种选择 

那么我们可以想到转化为二进制来区分他们的状态

如果有放为1 没放为0

因此状态最多可以达到2ⁿ种（每个格子都放）

所以我们预处理出所有的状态 之后在进行DP详细的判断即可

代码

#include<iostream> using namespace std; #define ll long long ll f[20][2000][155]; ll ans; int num[2000],s[2000],n,k,cnt;//num为每种状态可以防止的国王数 //s为状态 void pre() { for(int i=0;i<(1<<n);i++)//枚举所有状态 { if(i&(i<<1)) continue;//如果冲突了 就跳过 //这里可以看成同一行里连着放了2个不满足 int sum=0;//国王数 for(int j=0;j<n;j++)//统计此状态放置的国王的个数 if(i&(1<<j)) sum++;//有放则为1 s[++cnt]=i;//添加状态 num[cnt]=sum;//统计国王数 } } void dp() { f[0][1][0]=1;//初始化 for(int i=1;i<=n;i++)//枚举行 for(int j=1;j<=cnt;j++)//枚举此行状态 for(int sum=0;sum<=k;sum++)//枚举前i行的国王数 { if(sum>=num[j])//如果前i行的国王数大于这种状态要放的国王数 //说明可以用这种状态 { for(int t=1;t<=cnt;t++)//枚举第i-1行的状态 { if(!(s[t]&s[j])&&!(s[t]&(s[j]<<1))&&!(s[t]&(s[j]>>1))) //无冲突 f[i][j][sum]+=f[i-1][t][sum-num[j]];//加上之前的方案 } } } for(int i=1;i<=cnt;i++) ans+=f[n][i][k];//ans为第n行已经放完所有国王的所有状态的累计 cout<<ans; } int main() { cin>>n>>k; pre();//预处理 dp(); }

 

转载于:https://www.cnblogs.com/BrokenString/p/9806879.html

相关资源：JAVA上百实例源码以及开源项目