M - Little Pony and Harmony Chest
怎么感觉自己越来越傻了，都知道状态的定义了还没有推出转移方程。
首先这个a的范围是0~30 这里可以推出 b数组的范围 0~60
原因很简单，因为这个要求abs(b-a)) 尽量小，所以如果b>=60 那还不如用1 ，因为1 的数量是没有限制的，
当 b>60 abs(b-a)>30 所以相比 b>60 b==1 更优。
然后我们对质数进行状压，为什么要对质数进行状压呢，因为质数两两互质，而且每一个数都是由若干个质数组成。
所以我们可以用质数来对状态进行筛选。
因为b的范围是从1到58（如果要选59，则也可以选1），所以我们要打个表，来表示他是由哪些素数组成的。
为什么要这样呢，因为这样可以就可以快速判断出之前的状态是不是和这个有冲突（就是有没有相同的质数）
知道这些就差不多了，这个题目利用状压位运算来判断一个两两之间有没有公约数，方法很巧妙。
具体：
dp[i][s] 表示到第 i 个位置，之前的状态为 s 的最小代价，
初始化 dp[0][0]=0,其他都是不合理的状态，所以初始化为inf
首先枚举位置，其次枚举状态，然后在枚举这个位置所有可能的数。
路径的输出就是记录这个状态的放的数，和这个状态之前的状态，一个是记录状态一个是记录数。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + ;
typedef long long ll;
ll dp[][<<];
int is[][<<];
int pre[][<<];
int p[maxn], isp[maxn], m;
void init()
{
memset(p, , sizeof(p));
for (int i = ; i <= ; i++) p[i] = ;
for(int i=;i*i<=;i++)
{
if(p[i])
{
for(int j=i*i;j<=;j+=i)
{
p[j] = ;
}
}
}
m = ;
for(int i=;i<=;i++) if (p[i]) isp[++m] = i;
}
int sta[], a[];
vector<int>e;
int main()
{
int n; init();
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if (i%isp[j] == ) sta[i] |= ( << (j - ));//sta 数组表示选i这个数的限制条件，这个要好好理解。
}
}
memset(pre, -, sizeof(pre));
memset(dp, inf64, sizeof(dp));
dp[][] = ;//这个dp定义的是到第i个位置，数的状态为s的代价，
//如果dp == inf 说明是不合理的状态，因为如果是在0这个位置，所以当没有数的状态就是合理的而且代价==0
for(int i=;i<n;i++)//这个从0 开始是因为每次第i个更新第i+1个
{
for(int j=;j<(<<);j++)
{
if (dp[i][j] == inf64) continue;
for(int k=;k<=;k++)
{
if (sta[k] & j) continue;
int tmp = sta[k] | j;
if (dp[i + ][tmp] > dp[i][j] + abs(a[i+] - k))
{
dp[i + ][tmp] = dp[i][j] + abs(a[i+] - k);
is[i + ][tmp] = k;
pre[i + ][tmp] = j;
}
}
}
}
int ans=inf, id=;
for(int i=;i<(<<);i++)
{
if(dp[n][i]<ans)
{
ans = dp[n][i];
id = i;
}
}
for(int i=n;i>=;i--)
{
e.push_back(is[i][id]);
id = pre[i][id];
}
for (int i = e.size() - ; i >= ; i--) printf("%d ", e[i]);
printf("\n");
return ;
}
状压dp
这个题目我现在做感觉不是很简单，之前已经写过一次了，今天又写了一次还是感觉有点迷糊。
明确dp的定义dp[s][i]表示状态为s 上一个节点是i的最小代价。
路径的输出就是记录这一个点这个状态选择的值，再记录上一个点的状态。
根据这个dp定义的状态可以知道要枚举状态和点，先枚举点再枚举每一个点可能的状态，
最后枚举这个点的所有可能性。
先枚举状态不是很好写。