bzoj1863 [ZJOI2006]皇帝的烦恼

题目链接

problem

给出一个长度为(n)的环，第(i)个点需要分配(a_i)种颜色。相邻两个点不能有相同的颜色。求最少需要多少种颜色。

solution

挺巧妙的一个(dp)。

显然答案具有单调性，所以我们可以先二分一个答案(x)。

然后用(mn[i])表示第(i)个点与第(1)个点最少有多少个相同的颜色，用(mx[i])表示第(i)个点与第一个点最多有多少个相同的颜色。

然后考虑转移，对于(mn[i])，肯定要让(i-1)与(1)的相同颜色尽量多，才可以使(i)与(1)相同的颜色尽量少。然后考虑总共有(x)中颜色，在(1)与(i-1)相同颜色尽量多的情况下，还有(x-(a_1-a_{i-1}+mx[i-1]))种与(1)不同的颜色。那就让(i)先用这些颜色染，不够的就要用与(1)相同的颜色了。所以就有(mn[i] = max(0,a_i-(x-a_1-a_{i-1}+mx[i-1]))

然后转移(mx[i])，同理，如果想让(1)与(i)的相同颜色尽量多，那么就要让(i-1)与(1)的相同颜色尽量少，(i)可以与(1)相同的部分，就是(1)的颜色数量减去(1)与(i-1)颜色相同的部分。所以就有(mx[i]=min(a_i,a_1-mn[i-1]))。

PS：(n=1)时应当特判！(虽然数据没有卡)

code

/*
* @Author: wxyww
* @Date:   2020-04-22 18:53:27
* @Last Modified time: 2020-04-22 19:08:17
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
	ll x = 0,f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1; c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = getchar();
	}
	return x * f;
}
int mn[N],mx[N],n,a[N];
bool check(int x) {
	mx[1] = mn[1] = a[1];
	for(int i = 2;i <= n;++i) {
		mn[i] = max(0,a[i] - (x - a[1] - a[i - 1] + mx[i - 1]));
		mx[i] = min(a[i],a[1] - mn[i - 1]);
	}
	return mn[n] == 0;
}
int main() {
	n = read();
	int l = 0,r = 100000000;

	for(int i = 1;i <= n;++i) {
		a[i] = read();
		l = max(l,a[i] + a[i - 1]);
	}
	if(n == 1) {
		cout<<a[1]<<endl;return 0;
	}
	int ans = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) ans = mid,r = mid - 1;
		else l = mid + 1;
	}
	cout<<ans;
	return 0;
}