复健\(day4\)
动态规划（四）状压\(DP\)
题目中的要求与位运算相关的表示：
\(1.\)同一行不能有相邻的\(1\):\(if(!(i\&(i>>1)))\)
\(2.\)某一行不能与上一行的正上方左上方和右上方同时有\(1\)：\(!(a\&b)\)且\(!(a\&b>>1)\)且\(!(a\&b<<1)\)
\(3.\)统计\(i\)包含的\(1\)的个数：\(for(int j=0;j<n;j++) num[i]+=(i>>j\&1);\)
\(1.\)小国王
\(f[i][j][k]\)表示前\(i\)行已经放了\(j\)个国王，状态为\(k\)的方案数，用\(c[k]\)表示状态为\(k\)时放入的国王数
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 15
using namespace std;
int n,k;
int cnt;
int s[1<<maxn];//存储一行的合法状态
int num[1<<maxn];
long long f[maxn][maxn*maxn][1<<maxn];
int main()
{
cin>>n>>k;
for(int i=0;i<(1<<n);i++)
{
if(!(i&i>>1))
{
s[cnt++]=i;
for(int j=0;j<n;j++) num[i]+=(i>>j&1);//统计i包含的1的个数
}
}
f[0][0][0]=1;//不放国王也是一种方案
for(int i=1;i<=n+1;i++)
{
for(int j=0;j<=k;j++)
{
for(int a=0;a<cnt;a++)
{
for(int b=0;b<cnt;b++)
{
int c=num[s[a]];
if((j>=c)&&!(s[a]&s[b])&&!(s[a]&s[b]>>1)&&!(s[a]&s[b]<<1))
f[i][j][a]+=f[i-1][j-c][b];
}
}
}
}
printf("%lld\n",f[n+1][k][0]);//第n+1行什么都不放
}
\(2.\)炮兵阵地
https://www.luogu.com.cn/problem/P2704
还是先做预处理，处理出一行中合法的状态（也就是再相邻的三个格子里不能有两个1）\(!(i\&i>>1)\)且\(!(i\&i>>2)\)
行间合法为\(!(a\&b)\)且\(!(a\&c)\)且\(!(b\&c)\)
由于要使第\(i\)行在规定位置上放置，则\((s[a]\&g[i])==s[a]\)
\(f[i][a][b]\)表示第\(i\)行状态为\(a\)，第\(i-1\)行状态为\(b\)的最大数量
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 10
using namespace std;
int s[1<<maxn];
int g[110];
int cnt;
int num[1<<maxn];
int f[110][1<<maxn][1<<maxn];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
char c;
cin>>c;
if(c=='P') g[i]+=1<<(m-j-1);
}
}
for(int i=0;i<(1<<m);i++)
{
if(!(i&i>>2)&&!(i&i>>1))
{
s[++cnt]=i;
for(int j=0;j<m;j++) num[i]+=(i>>j&1);
}
}
for(int i=1;i<=n+2;i++)//多算两行时为了最终的最大数量方便表示
{
for(int a=1;a<=cnt;a++)
{
for(int b=1;b<=cnt;b++)
{
for(int c=1;c<=cnt;c++)
{
if(!(s[a]&s[b])&&!(s[a]&s[c])&&!(s[b]&s[c])&&(s[a]&g[i])==s[a]&&(s[b]&g[i-1])==s[b])
{
f[i][a][b]=max(f[i][a][b],f[i-1][b][c]+num[s[a]]);
}
}
}
}
}
printf("%d\n",f[n+2][1][1]);
}
\(3.\)玉米田
https://www.acwing.com/problem/content/329/
#include<iostream>
#include<cstdio>
#define maxn 15
using namespace std;
const int mod=1e8;
int s[1<<maxn];
int cnt;
int g[maxn];
int f[maxn][1<<maxn];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
int c;
cin>>c;
g[i]+=(c<<(m-j-1));
}
}
for(int i=0;i<(1<<m);i++)
{
if(!(i&i>>1)) s[++cnt]=i;
}
f[0][1]=1;
for(int i=1;i<=n+1;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int k=1;k<=cnt;k++)
{
if(!(s[j]&s[k])&&(s[j]&g[i])==s[j]&&(s[k]&g[i-1])==s[k])
{
f[i][j]=(f[i][j]+f[i-1][k])%mod;
}
}
}
}
printf("%lld\n",f[n+1][1]%mod);
return 0;
}
有个点一直没过，以为是没开\(long\) \(long\)，结果是忘了取模了（T^T)
\(4.\)蒙德里安的梦想
https://www.acwing.com/problem/content/293/
我们考虑按列摆放，某列的一行用\(0\)或者\(1\)表示摆放状态
如果某行是\(1\)表示横放，并且向下一列伸出
如果某行是\(0\)表示竖放，或者说这一格是由前一列伸出的（因为这样对于这一个格子来说相当于竖放）
合并两列状态后：不存在连续的奇数个\(0\)，则状态合法（因为我们竖放是\(2\times 1\)的规格，所以一列中相邻的\(1\)之间必须是偶数个\(0\)）
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 15
#define int long long
using namespace std;
bool st[1<<maxn];
int cnt;
int g[maxn];
int f[maxn][1<<maxn];
signed main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&(n!=0||m!=0))
{
for(int i=0;i<(1<<m);i++)
{
st[i]=true;
int cnt=0;//存放连续的0的个数
for(int j=0;j<m;j++)
{
if(i>>j&1)
{
if(cnt&1)
{
st[i]=false;
break;
}
}
else cnt++;
}
if(cnt&1) st[i]=false;//处理高位0的情况，比如0100
}
memset(f,0,sizeof(f));
f[0][0]=1;
//第0列不横放是一种合法状态
for(int i=1;i<=n;i++)
{
for(int j=0;j<(1<<m);j++)
{
for(int k=0;k<(1<<m);k++)
{
if((j&k)==0&&st[j|k])//j&k==0指两列不出现重复的1，因为对于一个横放的块，其第二列状态其实是0
{
f[i][j]+=f[i-1][k];
}
}
}
}
printf("%lld\n",f[n][0]);
}
return 0;
}