[状压DP]车
2024-09-01 04:39:40
车
车
车
题目描述
在
n
∗
n
n*n
n∗n(
n
≤
20
n≤20
n≤20)的方格棋盘上放置
n
n
n个车(可以攻击所在行、列)，有些格子不能放,求使它们不能互相攻击的方案总数。
输入
第一行为棋盘的大小
n
n
n
第二行为障碍的数量
m
m
m
第三行到第
m
+
3
m+3
m+3为
m
m
m个障碍
输出
总数
样例输入
4
2
1 1
2 2
样例输出
14
题目解析
首先，我们看题，想到可以用
D
P
DP
DP来做。以
f
[
i
]
[
j
]
f[i][j]
f[i][j]来储存位置
i
,
j
i,j
i,j的状态。
但考虑到要考虑到棋盘的状态，所以要用状压DP。
状压DP是以DP为基础，将二维压至一维，转化为十进制存储至数组里
然后，我们将
f
[
i
]
[
j
]
f[i][j]
f[i][j]压至一维，并且以一个数值
p
[
i
]
p[i]
p[i]表示
2
2
2的
i
i
i次方
通过一个
a
a
a数组来表示障碍的状态。
通过一位巨佬的指教，我得出了一个转移
a
[
x
]
=
p
[
y
−
1
]
a[x]=p[y-1]
a[x]=p[y−1]
然后以一个c来记录当前的行数，得到状态转移方式
for(t=i & ~a[c];t;t-=t & (-t))
f[i]+=f[i^(t & (-t))];
（其中
1
1
1是不能放，表放过或有障碍；
0
0
0是可以放）
code
#include<stdio.h>
#include<iostream>
using namespace std;
long long n,m,x,y,t,c;
long long a[25],p[25],f[1<<20]={1};
int main ()
{
scanf ("%lld%lld",&n,&m);
p[0]=1;
for (long long i=1;i<21;++i) p[i]=p[i-1]*2;
for (long long i=1;i<=m;++i)
{
scanf ("%lld%lld",&x,&y);
a[x]+=p[y-1];
}
for (long long i=1;i<p[n];++i)
{
for(c=0,t=i;t;t-=t & (-t))c++;
for(t=i & ~a[c];t;t-=t & (-t))
f[i]+=f[i^(t & (-t))];
}
printf ("%lld",f[p[n]-1]);
return 0;
}
最新文章
- 如何完全卸载OneDrive （Windows 10 64bit）
- AngularJs $interpolate 和 $parse
- WAF绕过的技巧
- RedHat/CentOS系统信息查看命令大全
- fixSidebar简介与修正log
- 开发库比较(3) - Mobile Web 开发 - Sencha, jquerymobiel, phonejs, jqtouch, jqmobi
- JS 拼凑字符串
- 我用过的Linux命令--虚拟机和宿主机的网络连接方式
- GDOI2015——已成梦
- Atitit.jquery 版本号新特性attilax总结
- node里面的c/c++模块
- C++闭包： Lambda Functions in C++11
- hystrix 请求合并（6）
- Linux学习路线全解，Linux操作系统学习路线
- HDU1711 Number Sequence（KMP模板题）
- JAVA SpringBoot 项目打包（JAR），在打包成 docker 镜像的基本方法
- 如何在 Xcode 中修改应用的名字
- Linux文件描述符
- ASP.NET MVC 获取计算机字体
- 推荐一个在线json数据格式化网站