一、基于棋盘式(连通性)的状态压缩问题
1064. 小国王
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;//应该是溢出了对吧，所以我们要把所有的f改成long long
const int N=12;//待会儿我会给大家解释一下为什么要开到12
const int M=1<<10,K=110;//K是我们的国王数量
int n,m;//这里用m来表示国王数量，因为我习惯用n来表示一个数然后m来表示另外一个值
vector state; //state 用来表示所有的合法的状态
int id[M];//id的话是存这个每一个状态和这个它的下标之间的映射关系 id有用到吗？好像没有用到
//应该是我之前写的时候思路不太一样，想的时候可能，就是前面设计的思路和实际用到的思路可能会有一点区别
//所以这里其实是不要加id i 的
vector head[M];//这个是每一状态所有可以转移到的其他状态
int cnt[M];/*然后cnt的话存的是每个状态里面 1 的个数，因为我们刚才我们的状态转移方程里面，
其实有一个需要求这个每一个状态里面1的个数的一个过程对吧*/
LL f[N][K][M];//这就是我们刚才说的那个状态表示
bool check(int state)
{
for(int i=0;i> i & 1)&&(state >> i + 1 & 1))
return false;//如果存在连续两个1的话就不合法
return true;//否则的话就是合法的
}
int count(int state)//这里y总没具体解释，我补充一下，这里就是计算某个数二进制里面1的个数
{
int res=0;
for(int i=0;i>i&1;
return res;
}
int main()
{
cin>>n>>m;
//首先我们需要把所有合法状态处理出来对吧，把它预处理一下
for(int i=0;i<1<=c)//如果数说满足要求的话，那么我们就可以转移了
{
f[i][j][a]+=f[i-1][j-c][b];
//转移的话就是f[i][j][a]+=f[i-1][j-c][b]，然后从b转移过来
}
}
//好，那我们最终的答案是什么呢？
//我们的最终的答案应该是这个f[n][m][ ]，然后最后一维可以直接去枚举对不对
//去枚举一下最后一维是从，就是所有合法状态都是可以的，就最后一行它所有合法状态都是可以的对不对
//那这里的话我们可以偷个懒，不是偷个懒，我们可以有个小技巧，就是我们在枚举i的时候,枚举到n+1就可以了
//就是我们去算到第i+1行，假设我们的棋盘是一个n+1 * n的一个棋盘，多了一行
/*那么我们最终算的时候 就需要输出一个 f[n+1]，就是第n+1行，
一共摆到了第n+1行，然后m，然后0，因为第n+1行一个都没摆，对吧*/
cout<
327. 玉米田
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 15,M = 1<<12,mod = 1e8;
int m,n;
int g[N];
vectorv; //存放所有一行内的合法方案
vectorhead[M];//存放所有合法方案的合法转移
LL f[N][M];//f[i][j]:前i行土地中，最后一行状态为j的所有方案个数
bool check(int state)//检查一行内状态的合法性
{
for (int i = 0; i < n; i ++ )
{
if(state>>i & 1 && state>>(i+1) & 1) return false;//相邻不能种
}
return true;
}
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i ++ )
{
int t;
for (int j = 0; j < n; j ++ )
{
scanf("%d", &t);
g[i] += (t<
292. 炮兵阵地
解法1:滚动数组
#include
#include
#include
#include
using namespace std;
const int N = 110,M = 1<<11;
vectorv;
int g[N];
int f[N][M][M];//f[i][j][k]:考虑前i行，最后一行状态为j，倒数第二行状态为k的方案的炮兵个数的最大值
int cnt[M];//二进制中1的数量
int n,m;
int count(int state) //计算1的数量
{
int res = 0;
for(int i = 0;i>i & 1);
return res;
}
bool check(int state)//检查一行内状态的合法性
{
for(int i = 0;i>i & 1) && ((state>>i+1 & 1)|(state>>i+2 & 1))) return false;
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
char c;
for (int j = 0; j < m; j ++ )
{
cin>>c;
if(c=='H') g[i] += (1<
合法转移预处理+滚动数组优化
#include
#include
#include
#include
using namespace std;
const int N = 110,M = 1<<11;
int f[2][M][M];
int n,m;
int g[N];
int cnt[M];
vectorv;
vectorhead[M];
bool check(int state)
{
for(int i = 0;i>i & 1) && ( (state>>i+1 & 1) || (state>>i+2 & 1) ) ) return false;
}
return true;
}
int count(int state)
{
int res = 0;
for(int i = 0;i>i & 1);
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
char c;
for (int j = 0; j < m; j ++ )
{
cin>>c;
if(c=='H') g[i] += (1<
二、基于集合的状态压缩DP
524. 愤怒的小鸟
#include
#include
#include
#include
#define x first
#define y second
using namespace std;
typedef pair PDD;
const int N = 18, M = 1 << 18;
const double eps = 1e-8;
int n, m;
PDD q[N];
int path[N][N];
int f[M];
int cmp(double x, double y)
{
if (fabs(x - y) < eps) return 0;
if (x < y) return -1;
return 1;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;
memset(path, 0, sizeof path);
for (int i = 0; i < n; i ++ )
{
path[i][i] = 1 << i;
for (int j = 0; j < n; j ++ )
{
double x1 = q[i].x, y1 = q[i].y;
double x2 = q[j].x, y2 = q[j].y;
if (!cmp(x1, x2)) continue;
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
if (cmp(a, 0) >= 0) continue;
int state = 0;
for (int k = 0; k < n; k ++ )
{
double x = q[k].x, y = q[k].y;
if (!cmp(a * x * x + b * x, y)) state += 1 << k;
}
path[i][j] = state;
}
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 0; i + 1 < 1 << n; i ++ )
{
int x = 0;
for (int j = 0; j < n; j ++ )
if (!(i >> j & 1))
{
x = j;
break;
}
for (int j = 0; j < n; j ++ )
f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
}
cout << f[(1 << n) - 1] << endl;
}
return 0;
}