https://codeforces.com/contest/1400

E. Clear the Multiset

题意：给定 n 个数，两种操作：任选一个区间，区间中所有数 -1；任选一个数，这个数减去任意值。不能出现负数。问最少操作次数使得所有数变为 0。

分治

由于不能出现负数，所以对于某个区间，第一种操作最多进行次数为该区间最小值。操作后该区间分裂为两个区间，再各自进行操作。

以最小值点 p 为分割点，分治左右区间。分裂的代价有两种：操作一进行多次，或直接进行一次操作二。这两种方式得到左右区间的不同之处在于：第一种方式会使得所有数减去最小值。需要记录下来最终结果为两者取最小值。即 min(dfs(l,p−1,−a[p])+dfs(p+1,r,−a[p])+a[p]+ad,dfs(l,p−1,ad)+dfs(p+1,r,ad)+1)min(dfs(l,p-1,-a[p])+dfs(p+1,r,-a[p])+a[p]+ad,dfs(l,p-1,ad)+dfs(p+1,r,ad)+1)。

但是这样复杂度太大。

第二种分裂方式可以直接改为 r−l+1r-l+1，也就是说只要在这个区间上进行了操作二，那么在分裂得到的左右子区间上也必定继续使用操作二，所以最终代价就是对这个区间上所有数都只使用操作二。

用另一道原题来说明更方便 CF448C ：刷篱笆，可以横着刷，或者竖着刷，刷子宽度为 1 ，要求用最小的次数刷完所有篱笆。题意是一样的，只是改成刷篱笆。

现在找到一处最矮的篱笆在 p 处。

首先要知道，如果决定在 p 处横着刷，那么必定会把整个 p 横着刷完，否则还需要竖着刷一次，还不如一开始就竖着刷，即使假设左右区间确实需要横着刷一定高度，那么这高度不可能小于 p 处，因为即使小于 p，由于 p 处是整个区间最矮的地方，所以多刷的高度也不会对结果有影响（并不会使得某区间被截断）。

如果在 p 处竖着刷，则两边不会再横着刷。假设左右区间中某一边存在某处横着刷，那么向上面所说的，那处必定会横着刷完，那么完全可以顺带着把 p 处刷完，也就是 p 处一开始就没必要竖着刷了。

有些博客里把只需要 r-l+1 的原因归结为这是一个上界。这是不对的，因为它虽然是上界，但不一定是上确界，如果先竖着刷，再横着刷的方法确实能够得到更小的解，那么把它排除掉就会导致缺失一种解，而这与 r-l+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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n;
int a[5010];
int amin[5010][5010];
int dfs(int l, int r, int ad) {
	if (l > r)return 0;
	int p = amin[l][r];
	return min(r - l + 1, dfs(l, p - 1, -a[p]) + dfs(p + 1, r, -a[p]) + a[p] + ad);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		amin[i][i] = i;
		for (int j = i + 1; j <= n; j++) {
			if (a[j] < a[amin[i][j - 1]])amin[i][j] = j;
			else amin[i][j] = amin[i][j - 1];
		}
	}
	printf("%d\n", dfs(1, n, 0));
	return 0;
}