【泛学笔记】动态规划杂项

其实就是听课笔记,但后来发现没啥可听的就变成了做题笔记(?)

单调队列部分

单调队列主要用来优化,对于状态 $\rm S$ 的某个后继状态 $\rm S’$,如果 $\rm S’$ 比 $\rm S$ 更优就可以舍弃掉 $\rm S$ 的转移。通常表现形式为会有限制,比如

其中 $\{L\}$ 是一个给定常数,且 $\forall i, L_i\geq L_{i-1}$ 。那么可知对于后续状态 $s_i$ ,他的可转移范围一定更大,至少比 $s_j$ 大,所以可以删除 $s_j$.

多重背包

考虑原本的转移

其中需要优化掉的是 $k$ 这一维,发现他原本并没有任何对于转移单调的限制,于是考虑变一下形。

令 $d=j\bmod w_i$,$s=\lfloor\frac{j}{w_i}\rfloor$,那么转移就可以写作

发现转移条件 $s-k\leq c_i\Longrightarrow k\geq s-c_i=\lfloor\frac{j}{w_i}\rfloor-c_i$ ,可知 $L_j$ 不降,于是就对每个 $d$ 用单调队列即可。

斜率优化部分

这部分虽然简单但是不熟,所以可能需要多做点题。

傻狗题

把一个长为 $n$ 的正整数序列划分成若干段,每一段的代价是内部元素和的平方加上一个定值 $m$。求划分整个序列的最小代价。

可知转移

于是就变成了有一个以 $s_i$ 为斜率,$f_j+s_j^2$ 为纵坐标,$s_i$ 为横坐标的斜率优化。考虑横坐标和斜率都是单调的,就可以直接队尾删/队尾插入。

[USACO08MAR]Land Acquisition

有 $n$ 块长方形的土地需要购买,你每次可以选择一组土地一起购买,价 格为这些土地中最大的长乘以最大的宽。求购买所有土地的最小费用。

$n ≤ 50000$

考虑先排序,然后考虑如果直接 $dp$,那么本身需要枚举 $i\sim j$ 之间的元素取 $\max$,这样显然复杂度就多了一维 $n$。仔细思考后发现,如果对于一组 $(i,j)$,满足 $w_i\geq w_j$ 且 $h_i\geq j_j$ ,那么就可以删掉 $j$ 。具体的,考虑按照 $h$ 排序之后,用一个单调栈来维护这个东西。

那么这样最后剩下的一定满足 $w$ 单调。所以就会得到类似

那么令 $h_{j+1}$ 作为横坐标,横坐标单调;$w_i$ 作为斜率,斜率单调。于是就变成了最 general 的斜率优化问题。

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
typedef long long LL ;

const int N = 100010 ;

int n ;
int top ;
LL f[N] ;
deque <int> q ;
struct grid{
LL x, y ;
}base[N], t[N] ;

bool comp(grid a, grid b){
return a.x == b.x ? a.y > b.y : a.x > b.x ;
}
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%lld%lld", &base[i].x, &base[i].y) ;
sort(base + 1, base + n + 1, comp) ;
for (int i = 1 ; i <= n ; ++ i)
if (!top || t[top].y < base[i].y) t[++ top] = base[i] ;
// for (int i = 1 ; i <= 50 ; ++ i) cout << t[i].x << " " << t[i].y << endl ;
n = top ; q.push_back(0) ;
for (int i = 1 ; i <= n ; ++ i){
while (q.size() > 1){
int o, p ; p = q.front() ; q.pop_front() ; o = q.front() ;
if (f[p] - f[o] <= t[i].y * (t[o + 1].x - t[p + 1].x))
{ q.push_front(p) ; break ; }
}
f[i] = f[q.front()] + t[q.front() + 1].x * t[i].y ;
while (q.size() > 1){
int o, p ; p = q.back() ; q.pop_back() ; o = q.back() ;
if ((f[p] - f[o]) * (t[p + 1].x - t[i + 1].x) <= (f[i] - f[p]) * (t[o + 1].x - t[p + 1].x))
{ q.push_back(p) ; break ; }
}
q.push_back(i) ;
}
cout << f[n] << endl ; return 0 ;
}

BTW,如何推凸包的维护方式,可以考虑是维护下凸壳还是上凸壳,但是似乎又一种方式更简便:

令 $0\leq k<j<i$ ,那么如果 $j$ 比 $k$ 好,那么需要满足

这么做就会比较直观?

值得注意的是,斜率优化的时候很可能会因为移项的时候符号变错了而GG。

还有,似乎如果斜率和横坐标的单调方式相同,那么就可以用单调栈替换掉单调队列。虽然…没啥用233

期望相关

Red is Good

$n$ 张红牌,$m$ 张黑牌随机打乱顺序放在桌面上,你可以翻牌,翻到红色则得到 $1$ 元,黑色则失去 $1$ 元。求在最优策略下平均能得到多少钱。

$n,m\leq 5000$

考虑如何设状态为 “已经xxx了”,不是很容易转移。于是考虑令 $f_{i,j}$ 为剩下 $i$ 张红的,$j$ 张黑的时的最大值。注意到由于是最优决策,所以有

[HNOI2015]亚瑟王

有 $n$ 张卡牌,玩 $r$ 轮游戏。每轮游戏从左向右轮流考虑每张没有发动过的卡牌,考虑到第 $i$ 张卡时,它有 $p_i$ 的概率发动并产生 $d_i$ 的贡献, 然后本轮立即结束并进入下一轮。若没有卡牌发动则直接进入下一轮。 $T$ 组数据,求期望贡献。

$T\leq 500, n\leq 300,r\leq 200$

考虑分别计算出每张卡牌的发动概率,然后分别乘上每张卡牌的权值得到答案。

具体的,令 $f_{i,j}$ 表示当前只在考虑第 $i$ 张牌,还剩 $j$ 次游戏没有开始的概率。考虑转移:

其实就是在计算牌 $i-1$ 是否被发动了,前半部分计算了第 $i$ 张牌在之后的 $j$ 次以及当前这一次中任意一次发动成功的概率,所以是 $1-一次也没发动成功的概率$;后半部分以此类推。注意,此处忽略了题目中「直接结束本轮」的约束。本质上,$f$ 保证了还有 $j$ 轮时,前 $i$ 张卡牌不会被选。

那么考虑如何计算第 $i$ 张牌是否发动了的概率:

之后用线性性算一下就好了。复杂度 $O(nTr)$。

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
int T ;
int n, r ;
double ans ;
double d[N] ;
double p[N] ;
double f[N][N] ;
double xs[N][N] ;

int main(){
cin >> T ;
while (T --){
cin >> n >> r ; double res ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%lf%lf", &p[i], &d[i]) ;
for (int i = 0 ; i <= n + 1 ; ++ i)
for (int j = 0 ; j <= r + 1 ; ++ j)
f[i][j] = xs[i][j] = 0 ;
f[0][r] = 1 ; ans = 0 ;
for (int i = 0 ; i <= n ; ++ i){
res = 1.0 ;
for (int j = 0 ; j <= r ; ++ j)
xs[i][j] = res, res *= (1.0 - p[i]) ;
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = r ; j >= 1 ; -- j)
f[i][j] = f[i - 1][j + 1] * (1.0 - xs[i - 1][j + 1]) + f[i - 1][j] * xs[i - 1][j] ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= r ; ++ j)
ans += d[i] * f[i][j] * (1.0 - xs[i][j]) ;
printf("%.9lf\n", ans) ;
}
return 0 ;
}