互不侵犯的king
状压dp题
每一行放不放国王可以用1010010来表示
所以每一行的状态可以看成一个二进制数
这样n是小于9的，可以把小于2^n，（因为2^9是512，很小）的数打表存出来
把自己和自己冲突的筛掉，然后记下有多少1，判断他们是否冲突。
预处理完了，接下来是dp了
动态转移方程：
dp[i][q+t[j]][a[j]]=Σdp[i-1][q][a[i]]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<stdlib.h>
using namespace std;
int cnt,ans;
int n,k,a[19999],dp[19][199][600];
int f[1999][1999],t[19999];
int main(){
scanf("%d%d",&n,&k);
int w=(1<<n)-1;
for(int i=0;i<=w;i++)
if((((i>>1)&i)==0)&&(((i<<1)&i)==0))
a[++cnt]=i;
for(int i=1;i<=cnt;i++)
{
int x=a[i];
while(x)
{
t[i]+=(x&1);
x/=2;
}
}
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
{
if(((a[i]&a[j])==0)&&(((a[i]>>1)&a[j])==0)&&(((a[i]<<1)&a[j])==0))
f[i][j]=1;
}
for(int i=1;i<=cnt;i++)dp[1][t[i]][a[i]]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=cnt;j++)
for(int q=1;q<=cnt;q++)
{
if(f[j][q])
for(int p=t[j];p+t[q]<=k;p++)
{
dp[i][p+t[q]][a[q]]+=dp[i-1][p][a[j]];
}
}
for(int i=1;i<=cnt;i++) ans+=dp[n][k][a[i]];
printf("%d",ans);
}
扫雷
某一位的状态可以由上面的和上上面的推过来
所以枚举第一位有没有雷
dp方程:
b[i]=a[i-1]-b[i-2]-b[i-1];1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<stdlib.h>
using namespace std;
int n,a[19999],b[19999], ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=0;i<=1;i++)
{
b[0]=0;
b[1]=i;
for(int j=2;j<=n+1;j++)
{
b[j]=a[j-1]-b[j-2]-b[j-1];
if(b[j]>1||b[j]<0)break;
if(j==n+1&&b[n+1]==0) ans++;
}
}
printf("%d",ans);
}
codevs
解药还是毒药
爆搜题
状态压缩
可以把要合并压缩为一个二进制数，1表示有病，0表示没病
分成两个数组
一个是治得a，一个是让他的病的b
a中0表示治，1表示不治
b中0表示不得，1表示得
用a中的对他&就是治他了，因为只又全是一才不治有病的，不会影响到1
用b中的对他|就是让他患病，因为只要有一个是1，就患病，也不影响本来就患病的
举个例子
10110101
&00001001
=00000001
看能治1,3,4,6的都被治了，而有病的不治8的还是有病，本来没病的2,5,7也没患病
10110101
| 00001001
=10111101
5都得病了，1,3,4,6,8也没好1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<queue>
using namespace std;
int n,m,a[19999],b[19999],s[19999],f[19999];
queue<int> q;
int bfs(){
f[(1<<n)-1]=1;
q.push((1<<n)-1);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=1;i<=m;i++)
{
int tmp=(x&a[i])|b[i];
if(tmp==0)
{
printf("%d",s[x]+1);
return 1;
}
if(!f[tmp])
{
f[tmp]=1;s[tmp]=s[x]+1;
q.push(tmp);
}
}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x;
for(int j=n-1;j>=0;j--)
{
scanf("%d",&x);
if(x==0||x==-1)
a[i]+=(1<<j);
if(x==-1)
b[i]+=(1<<j);
}
}
if(!bfs()) printf("The patient will be dead");
}