题解 P4409 【[ZJOI2006]皇帝的烦恼】

· · 题解

广告

蒟蒻的blog

正文

题意：给定n个集合的大小，问在相邻集合没有交集的情况下，并集的最小大小

题解：集合思想（外带图形解释，生动而形象）

如果是一条链，那么直接贪心，找出最大的相邻数的和就是答案。但是这个是一个环，即要避免与1集合的冲突。那么考虑二分+dp

设二分出来的并集大小为x。

维护一个minn[i]：表示在不与集合i-1冲突的情况下，集合i与集合1的最小冲突数量。

大概就是这个样子。。。

首先可以发现，不属于i-1集合也不属于1集合的元素是能选多少选多少的。由于求的是minn[i]，所以我们要使得\{ i-1 \}∪ \{ 1 \}的元素个数最小（因为这样的话能够不冲突的元素最多）而根据容斥原理（？？？），\{ i-1 \}∪ \{ 1 \} = \{i-1 \}+ \{ 1 \}- \{ i-1 \}∩ \{1 \}，即需要 \{ i-1 \}与\{ 1 \}冲突数量最大

所以还需要一个maxx[i]：表示在不与集合i-1冲突的情况下，集合i与集合1的最大冲突数量

然后状态转移方程就特别好写了：

        maxx[i]=min(a[i],a[1]-minn[i-1]);
        minn[i]=max(0,a[i]-(x-(a[i-1]+a[1]-maxx[i-1])));

这里解释一下：

对于minn[i]，我们已经解释过了，但是对于maxx[i]，我们来看一下图：

那么可以发现，maxx[i]其实就是把集合1剩下的部分全部占完（当然，可能占不完，因为最多占a[i]个），所以状态转移方程就是上面那个了。

最后贴一下代码，如果还有不懂的地方可以私信我哦~~~：

code:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[100005],l,r,maxx[100005],minn[100005];
bool check(int x)
{
    for(int i=2;i<=n;i++)
    {
        maxx[i]=min(a[i],a[1]-minn[i-1]);
        minn[i]=max(0,a[1]+a[i-1]-maxx[i-1]+a[i]-x);
    }
    if(!minn[n]) return true;
    else return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        l=max(l,a[i]+a[i-1]);
    }
    maxx[1]=minn[1]=a[1];
    r=300000;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}