状压dp被虐日记。
小国王
看范围知识状压。
其实基本这种联通性的问题都是。
好家伙伤不起啊。
状压三步走:
step1:设状态
大胆设就行。
f[i][j][k]
表示前i行放j个国王,状态为f的方案。
step2:转移条件
这个学了y总的方法:直接把状态和转移的地方记到vector
里面去。
然后的话就是要点了:
- 左右不相邻,这个可以写一个基础的
check
,暴力$O(n)$,抽风大佬的位运算做法$O(1)$ - 上下不相邻,直接与
- 斜对角不相邻,可以或玩之后直接进行
check
step3:写代码
代码里有比较详细的注释,供大家参考。
/*
f[i][j][k(压缩状态)]表示的是前i行j个国王状态为k
条件:上下两行不能都为1,左右一一样,斜对角也是
左右:直接检查
上下:与运算
斜对角:或运算
*/
//过于经典的卡常火车头
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
const int N = 12, M = (1 << N) + 10;
#define int long long
//恶心一下评测机
int n, k;//基础数值
int f[N][N * N][M];//dp数组
int cnt[M];//数量
vector<int> h[M];//可以转移到的
vector<int> alls;//所有的状态
bool check(int state)
{
//检查state是否满足没有左右相邻的状态
for(int i = 0; i < n; i ++)//小技巧,一定是n位的
{
//直接检查就行了。
if(state>> i & 1 && state >> (i + 1) & 1)
{
//位运算经典技巧。
return false;//有bug,不行
}
}
return true;
}
int count_k(int state)
{
//看看一个状态中国王的数量
int cnt = 0;
for(int i = 0; i < n; i ++)
{
if(state >> i & 1)
{
cnt ++;
}
}
return cnt;
}
main()//整掉评测姬后这里别加int了
{
cin >> n >> k;//读入
//第一步,处理状态,也就是预处理alls和cnt数组。
for(int i = 0; i < (1 << n); i ++)
{
if(check(i))
{
//记录一下状态
alls.push_back(i);
cnt[i] = count_k(i);
}
}
//第二步,预处理h数组
for(int i = 0; i < alls.size(); i ++)
{
for(int j = 0; j < alls.size(); j ++)
{
//开始检查
//先处理上下的,左右的之前已经统一做过一遍处理了。
if((alls[i] & alls[j]) == 0)
{
//接着我们枚举斜对角的
if(check(alls[i] | alls[j]))
{
//这状态没毛病,可以进行转移。
//对i->j建立一条转移的链
h[i].push_back(j);
}
}
}
}
//第三步,开始dp
f[0][0][0] = 1;//唯一的方案,一切的起点。
for(int i = 1; i <= n + 1; i ++)//小坑
{
for(int j = 0; j <= k; j ++)//小坑*2
{
//下面开始枚举两个状态并进行转移
for(int s1 = 0; s1 < alls.size(); s1 ++)
{
for(int s2 = 0; s2 < h[s1].size(); s2 ++)
{
if(j >= cnt[alls[s1]])
{
//终于可以进行转移了
f[i][j][s1] += f[i - 1][j - cnt[alls[s1]]][h[s1][s2]];
}
}
}
}
}
cout << f[n + 1][k][0] << endl;
return 0;
}
每日一WA,一遍再见
哈哈哈
你的头文件为什么变得这么长了hh
那是在卡常哈哈哈哈哈
师傅,我在用手机,QWQ
2124您做出来了吗?
我还没有啊啊啊啊啊
快了
压位之后就过了,现在海没有满分
o