摘要:二分后跑根据容斥转移的dp

[ZJOI2006]皇帝的烦恼

题面

题目分析

如果是一条链的话,直接贪心求出最大的相邻和即为答案.

然而题目是一个环,所以考虑最后一个集与第一个集的包含关系.

考虑二分出一个答案作为全集的大小,递推求解,设$min_i$为$\{i\} ~\cap~ \{i-1\} =0$的情况下,$\{i\} ~\cap~ \{1\}$的最小值.

因为要让$\{i\} ~\cap~ \{1\}$最小,所以要使i能够取的范围最大,我们需要使在{i-1}和{1}之外的元素最多,也就是最小化$\{i-1\} ~\cup~ \{1\}$.

根据容斥原理,我们知道:

$\{i-1\} ~\cup~ \{1\} = \{i-1\} + \{1\} - \{i-1\} ~\cap~ \{1\}$

{i-1}和{1}的大小是固定的,所以最大化$\{i-1\} ~\cap~ \{1\}$即可,我们设$max_i$为$\{i-1\} ~\cap~ \{1\}$的最大值.

现在考虑如何进行转移,对于$min_i$,我们用全集减去容斥原理求出的$\{i-1\} ~\cup~ \{1\}$,得到{i-1}和{1}之外的元素数量,用{i}减去这个数量就是必须与{1}相交的数量了,当然不能小于0.

对于$max_i$,很好发现用{1}减去$min_{i-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
51
52
53
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cmath"
#include "cctype"
#include "iomanip"
#include "time.h"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#include "algorithm"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=20010;
lxl n,l,r=INF,mid,ans;
lxl max_[maxn],min_[maxn],a[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline bool check(lxl limit)
{
for(R int i=2;i<=n;++i)
{
max_[i]=std::min(a[i],a[1]-min_[i-1]);
min_[i]=std::max((lxl)0,a[i]-(limit-(a[i-1]+a[1]-max_[i-1])));
}
return !min_[n];
}
int main(void)
{
n=read();
for(R int i(1);i<=n;++i)a[i]=read(),l=std::max(l,a[i]+a[i-1]);
min_[1]=max_[1]=a[1];
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))r=mid-1,ans=mid;
else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}