【听课笔记】决策单调性

决策单调性是老朋友了,这次稍微系统地重学了一次,顺便做了做之前没做的题。

四边形不等式

如果是最小值问题,那大概长这样:

那么如果满足这个,就说明其满足最小值时的决策单调性。证明起来很简单,因为 $a\to d,b\to c$ 的转移的值要更大些,所以 $a\to c,b\to d$ 的转移会更优,据此可得 $f$ 有决策单调性。

除此之外,该不等式存在一个变形。考虑对于 $a<b$ 的如下 $4$ 个量 $a,a+1,b,b+1$ ,如果满足下式:

那么也说明是满足四边形不等式的。证明的话可以考虑暴力归纳也好、换元消元也好,反正挺显然的。

例题

CF321E

你有⼀个 $n\times n$ 的对称矩阵表示不熟悉程度。

你要将它 $1\sim n$ 按顺序分成 $k$ 组,每组的代价为两两之间不熟悉程度的和。最小化这个东西。

$n \le 4000,k \le 800$

考虑拿四边形不等式来证明。对于 $a\leq b<c\leq d$ 而言,记 $s(a,c)$ 表示矩阵中左上角为 $(a,a)$ 右下角为 $(c,c)$ 的这么一个矩阵中元素的和,那么

注意到

那么就显然

十分满足决策单调性(其实画出图来更显然,就是多了两块矩阵)。

这个东西可以用分治来做。因为每一层决策与本层无关,即 $k-1\to k$ 。于是就可以 solve(l,r,ql,qr) 表示 $l\sim r$ 是从区间 $(ql\sim qr)$ 转移过来的。那么每次取 $mid=\frac{l+r}{2}$,然后找出 $f_{mid}$ 对应的最优决策所在位置,这样就可以分治了。复杂度 $O(nk\log n)$ 。

这题居然卡cin,气死我了

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
#define p_b push_back 
#define upb upper_bound
#define INF 0x3f3f3f3f

void debug(int *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ; cout << c ;
}

int n, k ;
int s[N][N] ;
int f[N][K] ;

int qr(){
int res = 0 ;
char c = getchar() ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c))
(res *= 10) += c - 48, c = getchar() ;
return res ;
}
int do_do(int l, int r){
return (s[r][r] + s[l - 1][l - 1] - s[r][l - 1] - s[l - 1][r]) >> 1 ;
}
void solve(int l, int r, int ql, int qr, int g){
if (l > r) return ;
int mid = (l + r) >> 1, pos = ql ;
for (int i = ql ; i <= qr && i <= mid ; ++ i){
if (f[i][g - 1] + do_do(i + 1, mid) < f[mid][g])
f[mid][g] = f[i][g - 1] + do_do(i + 1, mid), pos = i ;
}
//cout << mid << " " << pos << " " << g << endl ;
solve(l, mid - 1, ql, pos, g) ;
solve(mid + 1, r, pos, qr, g) ;
}
int main(){
cin >> n >> k ;
memset(f, 63, sizeof(f)) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
s[i][j] = qr() ; f[0][0] = 0 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] ;
for (int i = 1 ; i <= k ; ++ i) solve(1, n, 0, n, i) ;
cout << f[n][k] << endl ; return 0 ;
}

CF321E 的 $O(n^2)$ 做法

考虑记录一下每个点的决策范围。发现设状态 $(n,k)$ 最优决策位置记作 $opt(n,k)$ 的话,一定有

那么可以这么写:

1
2
3
4
for j : 1 to k
for i : n to 1
for p : opt(i, j - 1) to opt(i + 1, j)
if [f(p, j - 1) < f(i, j)] opt(i, j) = p, f(i, j) := f(p, j - 1) ;

考虑这么做的时间复杂度。

发现对于这个决策矩阵的每一条穿过 $opt(i,j)$ 和 $opt(i+1,j+1)$ 的斜线,每条斜线的代价是 $O(n)$ 的,原因是考虑斜线 $opt(i,j),opt(i+1,j+1)$ 这条斜线的决策来自于 $opt(i,j-1),opt(i+1,j)$ 这条斜线。那么也就是说,每个斜线的转移都是 $O(n)$ 的,共有 $O(n+k)$ 条斜线,所以复杂度 $O(n^2)$ 。

[NOI2009]诗人小G

有N个诗句需要被排版为若⼲⾏,顺序不能改变。⼀⾏内可以有若⼲个诗句,相邻诗句之间有⼀个空格。

定义⾏标准⻓度L,每⾏的不协调度为|实际⻓度-L|^P,整⾸诗的不协调度就是每⾏不协调度之和。

任务是安排⼀种排版⽅案,使得整⾸诗的不协调度最⼩。

$n\leq 10^5$ 。

考虑还是 $dp$ 嘛。以下分析暂不考虑什么 $\pm1$ 的常数问题。

$f_{i} $ 表示考虑了前 $i$ 个句子的最小不协调度。那么就有 $f_{i}=\min\{f_{j-1}+|s(i,j)-L|^P\}$。


考虑这个东西的性质。还是设 $a\leq b<c\leq d$ ,那么可知 $|s(a,c)-L|^P+|s(b,d)-L|^P$

草为什么我想直接打个表走人 来让我瞎编一下。令 $x=s(a,c)-L,y=s(b,d)-L$。那么要证明

考虑当 $|P|$ 为偶数的时候……


好的,上面的证明崩掉了。考虑另一种证明方法。考虑对于 $a<b$ 的如下 $4$ 个量 $a,a+1,b,b+1$ ,考虑去证明

发现令 $p = len_a,q=len_b,x=s(a,b)$本质上就是在证明

那么也就是要证明 $f(x)=|x|^z-|x-p|^z$ 这个函数是单调不降的。可知一定有 $s(a,b)>p+q$ ,所以可知括号内均 $>0$,换言之 $f(x)=x^z-(x-p)^z$ ,这显然是单调不降的。于是证毕。

但是这个地方存在一个问题,就是转移有着严格的顺序,不能像上一道题一样来分治,因为 $l$ 必须要先于 $mid$ 来转移。于是这显然就需要CDQ分治了 然而CDQ分治是 $\log ^2$ 的并不可以过得去(并且显然没人会这么写)。

所以此处就需要用二分+单调栈的方式来维护。这两个过程严格意义上是分开的。大概就是考虑对于每个转移完的 $i$ ,我们用这个去更新后面的点的决策区间,更新方法是:1、先不断比较当前的决策区间和之前每个数的决策区间哪个更优,维护一个从底部到顶部单调递减的栈,依次弹掉这些不优的;2、之后考虑二分栈顶的这一段,确定新一个决策点的左区间。

然后是实现细节方面。注意需要在维护单调栈的时候顺便维护每个元素的决策左区间,并且还要维护一个指针,用来寻找当前点的决策点。

然后还有十分神必的一点,就是要记得不将那些无有效决策区间的决策点入栈。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
int T ;
int top ;
ll f[N] ;
int kts[N] ;
int stk[N] ;
int pos[N] ;
int sum[N] ;
int base[N] ;
int n, p, k ;
char s[N][40] ;

ll expow(ll a, int b){
ll ret = 1 ;
while (b){
if (b & 1)
ret *= a ;
a *= a ; b >>= 1 ;
}
return ret ;
}
ll mabs(ll x){
return x > 0 ? x : -x ;
}
ll calc(int l, int r){
return expow(mabs(sum[r] - sum[l - 1] - k), p) ;
}
ll trans(int p, int x){
return calc(p + 1, x) + f[p] ;
}
void debug(int *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ; cout << c ;
}
int main(){
cin >> T ;
while (T --){
cin >> n >> k >> p ;
stk[top = 0] = 0 ; ++ k ;
memset(f, 0, sizeof(f)) ;
for (int i = 1 ; i <= n ; ++ i){
pos[i] = 0 ;
scanf("%s", s[i] + 1) ;
base[i] = strlen(s[i] + 1) ;
sum[i] = sum[i - 1] + base[i] ;
}
for (int i = 1 ; i <= n ; ++ i) sum[i] += i ;
//debug(sum, 1, n, '\n') ;
kts[0] = 1 ; int h = 0 ;
for (int i = 1 ; i <= n ; ++ i){
while (h < top && kts[h] < i) ++ h ;
if (kts[h] > i) -- h ;
f[i] = trans(stk[h], i) ; pos[i] = stk[h] ;
while (top && trans(stk[top], kts[top]) >= trans(i, kts[top]))
stk[top] = 0, kts[top] = n + 1, -- top ;
int l = kts[top], r = n + 1, mid, ans = n + 1 ;
while (l <= r){
int mid = (l + r) >> 1 ;
if (trans(stk[top], mid) >= trans(i, mid))
ans = mid, r = mid - 1 ; else l = mid + 1 ;
}
//cout << ans << " * " << endl ;
if (ans <= n) stk[++ top] = i, kts[top] = ans ;
//cout << i << " " << ans << endl ;
//debug(stk, 1, top, '\n') ;
//debug(kts, 1, top, '\n') ;
}
//debug(pos, 1, n, '\n') ;
if(f[n] > 1e18) {
puts("Too hard to arrange") ;
puts("--------------------") ; continue ;
}
cout << (long long)f[n] << endl ;
int t ; stk[top = 0] = t = n ;
while (t) stk[++ top] = t = pos[t] ;
while (top){
for (int i = stk[top] + 1 ; i < stk[top - 1] ; ++ i)
printf("%s ", s[i] + 1) ; printf("%s\n", s[stk[top - 1]] + 1) ; -- top ;
}
puts("--------------------") ;
}
return 0 ;
}

总之呢,单调栈+二分这个做法是比较普适的,但是有时候也可以写分治,因为分治比较好写。

IOI2013 wombats

题意⼤概是,有 $r\times c$ 的⽹格图,每次只能朝左右下三个⽅向。

操作包括修改⼀条边的边权,然后查询某两点之间最短路。

$r\leq 5000,c\leq 200,q\leq 200000,m\leq 500$ 其中 $m$ 是修改次数,$q$ 是询问次数。

草,这题真是从一开始就不会qaq

大概就是考虑以列为标号建线段树,然后每个区间维护最左边的点到最右边的所有点的最短距离。然后合并显然就是 $c^3$ 的,总复杂度 $O(rc^3+q\log r+mc^3\log r)$ 。(好像杜爷写的是 $O(rc^3+q+mc^3\log r)$

然后考虑这东西由于只能向右和向下走,所以是有单调性的,也就是对于右侧的两个点 $(x,y)$ 和 $(x,y+1)$ ,他俩的决策路线一定是不相交的。这个好像还是比较显然的?然后就可以暴力 $O(rc^3+q+mc^2\log c\log r)$ 做了。

不过显然根据上面那个 trick ,二维的决策单调性是可以消掉 $\log $ 的,还是上面那种做法。仔细想了想,其实 $nk$ 应该算是两维的决策单调性,所以或许这确实是二维决策单调性的通用解决方法吧。

嗯,代码是不想写了,就这样吧。

IOI2014 Holiday

有 n 个城市,每个城市有⼀个权值,起点在 s 。 每⼀天你可以往左或者往右⾛⼀步,或者选择游览这个城市。问 d 天能获得的最⼤权值和是多少?

发现一共至多有四种走法,就是一直向右走、一直向左走、向左走折回起点然后向右走、向右走折回起点然后向左走。前两种就显然是枚举走了 $k$ 个城市,然后找其中的前 $d-k$ 大的城市游览即可。

考虑另外两种的做法。先给出结论,假设我向右走到了点 $i$ ,再向左走到点 $j$ ,那么随着 $i$ 增大,$j$ 是不降的。

但这个地方很迷,迷在网上很多题解写的是决策单调性不是这东西单调,是前两种那个走法单调,我寻思这不是显然…

哦,想了想,发现本质是一样的。就是向右走 $0$ 再向左右显然也有单调性。那么现在唯一的问题就在于这个单调性似乎不是那么显然…

好的,那看起来是,随着 $l$ 不断向右,$r$ 不会向左(鬼知道我刚才怎么理解的)。这样就非常合理了。于是就可以分治去做了。复杂度 $m \log n$ 。