2019暑期集训第七讲：动态规划(II)
DP
状压DP
首先回顾一下位运算
- 与 &
- 或 |
- 异或 ^
- 取反 ~
- 左移 <<
- 右移 >>
^ 运算的逆运算是它本身
取反是对 1 个数 $num$ 进行的计算，~ 把$num$种的0 和 1 全部取反
补码——正数的补码是其（二进制) 本身，负数的补码是其（二进制）取反后加一
右移在C++中将直接舍弃右侧多余位，左侧则较为复杂，无符号数会在左侧补0，对于有符号书，则会用最高位的数补齐
[注]：
1. 左移和右移是有返回值的，并非对$num$本身进行操作
2. 左移和右移优先级低于四则运算，`x<<1+1` 会被解释为`x<<(1+1)`，所以一般最好都加上括号
一些应用
num<<i相当于$num\times 2^i$ ，而num>>i相当于$num \div 2^i$ 。效率要比 % 和 / 操作快得多（60%？）- 当$num>0$时两者并没有差别，但是当$num<0$时，普通除法时向0取整，而右移是向下取整
num * 10 = (num << 1) + (num << 3)- num & 1 取num二进制末尾，判断奇偶性
- 对应于集合上的运算
| 操作 | 集合表示 | 位运算语句 |
|---|---|---|
| 交集 | $a\cap b$ | a&b |
| 并集 | $a\cup b$ | a |
| 补集 | $\overline a$ | ~a |
| 差集 | $a\setminus b$ | ~a |
| 对称差 | $a\triangle b$ | a^b |
1 | //遍历一个集合的子集 |
好了开始正题
状压DP是DP的一种，通过状态压缩为整数来优化转移
直接上题
题目链接
在$N\times N$ 的棋盘里面放 $K$个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共$8$ 个格子。
$1\le N\le 9,0\le K\le N*N$
$f(i,j,l)$来表示前 $i$ 行，当前状态为$j$ ，且已经放置 $l$个国王时的方案。
$j$ 这一维用二进制来表示
先预处理在一行上的所有合法状态（即排除同一行上两个相邻的情况），然后直接枚举这些来匹配上一行的状态即可。
$f(i,j,l) = \sum f(i-1,x,l-num(x))$
$num(x)$ 为x在二进制下有多少个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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
typedef long long ll;
vector<int> sta,stan;
ll d[10][(1<<10)][100];
int n,k;
bool ok(int i,int j){
if(i & j)return false;
if((i << 1) & j)return false;
if(i & (j << 1))return false;
return true;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<(1<<n);i++){
int num = 0;
bool flag = true;
for(int j=0;j<n-1;j++){
if(i >> j & 1){
num++;
if(i >> (j+1) & 1){
flag = false;
break;
}
}
}
if(!flag)continue;
sta.push_back(i);
stan.push_back(num + (i >> (n-1) & 1));
}
for(int i=0;i<sta.size();i++){
d[1][i][stan[i]] = 1;
}
for(int i=2;i<=n;i++){
for(int j=0;j<sta.size();j++){
for(int t=0;t<sta.size();t++){
if(ok(sta[j],sta[t])){
for(int p = stan[j];p <= k;p++){
d[i][j][p] += d[i-1][t][p-stan[j]];
}
}
}
}
}
ll res = 0;
for(int i=0;i<sta.size();i++)
res += d[n][i][k];
cout<<res<<endl;
return 0;
}
不过瘾就再来一道
Mondriann’s Dream
求把$N*M(1\le N,M \le 11)$ 的棋盘分割成若干个$1\times 2$ 的长方形，有多少种方案。例如当 $N=2,M=4$时，共有5种方案。当$N=2,M=3$时，有3种方案。
NM只有11，八九不离十可以状压了，反正得挨个铺，所以从上到下考虑。假如现在铺好了前$i$ 层，基本思想就是从$i$ 层的状态转移到$i+1$层的状态。但是该如何表示？观察一下铺满第 $i$ 层的样子（必须保证第$i$层是满的，也就是说有的可以凸出来到$i+1$层但是要保证$i$层是满的）
对于第 i 行中竖着放的，第 $i+1$ 层要受到牵连，它必须补全竖着放置的上一半才行。但对于横着放的，第$i+1$层则无所谓。
所以我们可以用二进制中的 1 来表示他是否是竖着放置的上一半。为0则为其他状况。
$d[i][j]$表示第 $i$ 的形态为$j$ 时，前$i$ 行分割方案的总数。 $j$ 是用十进制整数记录的 $m$ 位二进制数。考虑$i+1$行的状态$k$在满足什么情况下转移是合法的。
- $j$中为 1 的位，$k$中必须为0
- $j$中为 0 的位，$k$中可以为1，但 k 要是为 0，就必须是连续的偶数个0（想一想为什么)
对于第一条，可以用 $i\&j = 0$ 来判断，对于第二条，有$z = i|j$，那么 z 的二进制表示中，每一段连续的 0 都必须有偶数个。（这些0代表若干个横着的 $1\times 2$ 长方形，奇数个0无法分割成这种形态。
1 |
|
数位DP
数位DP问题往往是这样的题型，给定一个闭区间$[l,r]$，让你求这个区间中满足某种条件的数的总数
又或者是求满足限制条件的第K小的数是多少。
- 首先我们将问题转换为更加简单的形式。设$ansi$ 表示$[1,i]$ 中满足条件的数的数量，那么所求的答案就是$ans_r-ans{l-1}$。
分开求解这两个问题即可。
对于一个小于$n$的数，它从高到底肯定出现某一位使得这一位上的数值小于$n$这一位上对应的数值。而之前的所有位都和$n$上的位相等。
有了这个性质，我们可以定义$f(i,st,op)$表示当前将要考虑的是从高到低的第$i$位，当前该前缀的状态为$st$（前一位或前几位的值），前缀和当前求解的数字的大小关系是op(op=1表示等于，op=0表示小于）时的数字个数。
题目链接
windy数
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道， 在A和B之间，包括A和B，总共有多少个windy数？$1 \le A \le B \le 2000000000$
1 |
|
Valley Number
当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。
比如，1，10，12，212，32122都是 Valley Number。
121，12331，21212则不是。
度度熊想知道不大于N的Valley Number数有多少。
注意，前导0是不合法的。
每组数据包含一个数N。
● 1≤T≤200
● 1≤length(N)≤100
结果对$1000000007$取模
1 |
|
POJ-3208 启示录
只要某数字的十进制表示中有三个6相邻，则该数字为魔鬼数，求第X小的魔鬼数$X\le 5e7$
这一类题目可以先用DP进行预处理，再基于拼凑思想，用“试填法”求出最终的答案
$F[i,3]$表示由 $i$ 位数字构成的魔鬼数有多少个，$Fi,j$ 表示由 $i$ 位数字构成的，开头已经有连续 $j$ 个6的非魔鬼数有多少个。（允许前导0的存在，想一想为什么）
转移方程
- $F[i,0] = 9*(F[i-1,0] + F[i-1,1] + F[i-1,2])$
- $F[i,1] = F[i-1,0]$
- $F[i,2] = F[i-1,1]$
- $F[i,3] = F[i-1,2] + 10 * F[i-1,3]$
然后一位一位的试填，要注意前面填过的数字结尾如果有 k 个6，通过后面拼接 3-k 个6也可以构成魔鬼数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
using namespace std;
typedef long long ll;
ll f[21][4];
int T,n,l;
void init(){
f[0][0] = 1;
for(int i=1;i<=20;i++){
f[i][0] = 9*(f[i-1][0] + f[i-1][1] + f[i-1][2]);
f[i][1] = f[i-1][0];
f[i][2] = f[i-1][1];
f[i][3] = f[i-1][2] + 10 * f[i-1][3];
}
}
int main(){
init();
scanf("%d",&T);
while(T--){
scanf("%d",&n);
//l为答案的长度
for(l=3;f[l][3] < n;l++);
//k表示填过的数字末尾有k个6
for(int i=l,k=0;i;i--){
for(int j=0;j<=9;j++){
ll cnt = f[i-1][3];//后面预处理出的魔鬼数
//找能够拼凑出来的魔鬼数
if(j == 6 || k == 3){
if(k == 3){
for(int x = 0;x < 3;x++)
cnt += f[i-1][x];
}else{
for(int x = max(3-k-1, 0);x<3;x++){
cnt += f[i-1][x];
}
}
}
if(cnt < n) n -= cnt;
else{
if(k < 3) j == 6 ? k ++ : k=0;
printf("%d",j);break;
}
}
}
cout<<endl;
}
return 0;
}
BZOJ1799 月之迷
给出两个数a,ba,b，求出$[a,b]$中各位数字之和能整除原数的数的个数。
我们按照模板的做法来想，枚举到第pos位时，要确定这一位的数字，可以更新现在所填数字的和，但对于最终的和无从得知，是否能整除也无从判别，我们试着先确定了最终的和，在枚举每一位的时候注意到，枚举x，则对最终和模数可以更新为 $(mod * 10 + x) \% sum$ ，所以可以想到每一次枚举一个和sum
$d[i][j][k]$表示 i 位数字，前面填过的数字和为 j 时，模sum为 k 的数字个数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
using namespace std;
typedef long long ll;
ll d[20][160][160],L,R;
int k[20],pos,mod;
//sum为之前填过的数字的和,p为之后要填的数字对mod的模为p
ll dfs(int pos,int sum,int p,bool lead,bool limit){
if(pos == -1){
if(p == 0 && sum == mod)return 1;
else return 0;
}
if(!limit && !lead && d[pos][sum][p] != -1)return d[pos][sum][p];
int up = limit ? k[pos] : 9;
ll res = 0;
for(int i = 0;i <= up;i ++){
if(lead){
if(i == 0){
res += dfs(pos - 1, sum + i, p, true, false);
}
else {
res += dfs(pos - 1, sum + i, (p * 10 + i) % mod, false, limit && i == k[pos]);
}
}
else {
res += dfs(pos - 1,sum + i, (p * 10 + i) % mod, false, limit && i == k[pos]);
}
}
if(!limit && !lead) d[pos][sum][p] = res;
return res;
}
ll solve(ll x){
pos = 0;
while(x){
k[pos++] = x % 10;
x/=10;
}
ll res = 0;
//mod为当前枚举的和
for(mod=1;mod <= pos * 9;mod++){
memset(d,-1,sizeof d);
res += dfs(pos-1,0,0,true,true);
}
return res;
}
int main(){
scanf("%lld%lld",&L,&R);
//cout<<solve(R)<<' ' <<solve(L-1)<<endl;
printf("%lld\n",solve(R)-solve(L-1));
return 0;
}
计数类DP
直接上题，跟之前的排列组合有比较大的联系
CF-559C Gerald and Giant Chess
给定一个 $H*W$的棋盘，棋盘上只有$N$ 个格子是黑色的，其他格子都是白色的。
在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动到黑色格子中。求这个卒从左上角移动到右下角，一共有多少种可能的路线
$1\le H,W\le 10^5,1\le N\le 2000$ 输出对$10^9+7$取模
H，W巨大，普通DP不用想，考虑如何用黑格子计数
由组合数学知识可知，从S到T的总路径条数为$C{H+W-2}^{H-1}$，只要减去至少经过一个黑格子的路径条数即为答案。
那么如何不重不漏的计数呢？
考虑每条至少经过一个黑格子的路径所包含的第一个黑格子，以4号黑格子(4,5)为例，从S到4号，总路径条数有$C{4+5-1-1}^{4-1}$条，只要排除掉经过3和经过1的路径条数即为从S到4，不经过黑格子的路径数。如何排除？其实我们之前已经算出来了，在算S到4的不经过黑格子路径条数时，已经分别算过了S到3，S到1的不经过黑格子路径条数，只要分别乘上由3到4，由1到4的所有路径数即可。
把所有黑色格子按照行列坐标递增的顺序排序，设$f[i]$ 为从S到第 $i$个格子，途中不经过其他黑色格子的路径数
在求解计数类动态规划时，通常要找一个“基准点”,围绕这个基准点构造一个不可划分的”整体”,以避免子问题之间的重叠
1 |
|
斜率优化DP
P3195 [HNOI2008]玩具装箱TOY
题目链接
设$d[i]$为将前 $i$ 个玩具装入箱中所需得最小费用
容易得到动态转移方程：
其中$s[i] = \sum_1^iC[i]$，普通DP复杂度为$O(n^2)$。经过斜率优化后将变为$O(n)$。
仔细观察我们便于表示可以令$f[i] = s[i]+i$
那么式子变成了
我们讨论$j_1，j_2(1\le j_1< j_2<i)$决策，假设$j_2$要比$j_1$更优，那么有
$d[j_1] + (f[i] -f[j_1]-1-L)^2 \ge d[j_2]+(f[i]-f[j_2]-1-L)^2$
展开后得到
$d[j_1] + f[i]^2 - 2\times f[i]\times (f[j_1]+1+L)+(f[j_1]+1+L)^2 \ge d[j_2]+f[i]^2-2\times f[i]\times (f[j_2]+1+L)+(f[j_2]+1+L)^2$
移项后可得
$2\cdot f[i]\ge {d[j_2]+(f[j_2]+1+L)^2-d[j_1]-(f[j_1]+1+L)^2 \over f[j_2]-f[j_1]}$
令$g[i] = f[i]+1+L$， 则有
$2\cdot f[i]\ge {(d[j_2]+g[j_2])-(d[j_1]+g[j_1])\over f[j_2]-f[j_1]}$
所以用一个队列维护决策集，当$j_1<j_2$，并且上式满足时，$j_1$ 出队。
又由于$f[i]$随$i$单调递增。所以计算$d[i]$之后要将 $i$ 入队时，要及时排除掉不可能作为决策的元素。
如何计算？队尾的斜率也要满足单调性，保持跟$f[i]$的单调性一致即可。
1 |
|
P2120 [ZJOI2007]仓库建设
题意：$1\sim N$ 号工厂，第$i$ 个工厂有$P_i$个成品，第$i$个工厂建立仓库需要$C_i$的费用，该工厂距离第一个工厂的距离为$X_i$，编号小的工厂只能往编号大的工厂搬用成品，每单位成品搬每单位距离需要花费1，问所有成品搬到工厂里面所需的最少费用是多少
分析
设$f[i]$ 为第 i 个工厂建立仓库，前 i 个工厂的成品都搬到仓库中的最小花费，则容易得到动态转移方程:
通式为
令 $s[i] = \sum_1^i P[i], ~~g[i] = \sum_1^iP_i\cdot X_i$,
则方程变为
则对于最优决策 $j$ ，有
也就是要找 $y = kx+b$，$k$已知，找一对$x,y$使得截距最小
由于$X[i]$是随$i$递增的，所以要维护的决策集的斜率也是递增的
1 |
|
