[BZOJ4709][JSOI2011]柠檬 (动态规划,决策单调性,二分)

发布于 2018-04-05  109 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4709][JSOI2011]柠檬 (动态规划,决策单调性,二分)

Description

Flute 很喜欢柠檬。它准备了一串用树枝串起来的贝壳,打算用一种魔法把贝壳变成柠檬。贝壳一共有 N (1 ≤ N ≤ 100,000) 只,按顺序串在树枝上。为了方便,我们从左到右给贝壳编号 1..N。每只贝壳的大小不一定相同,贝壳 i 的大小为 si(1 ≤ si ≤10,000)。变柠檬的魔法要求,Flute 每次从树枝一端取下一小段连续的贝壳,并选择一种贝壳的大小 s0。如果 这一小段贝壳中 大小为 s0 的贝壳有 t 只,那么魔法可以把这一小段贝壳变成 s0t^2 只柠檬。Flute 可以取任意多次贝壳,直到树枝上的贝壳被全部取完。各个小段中,Flute 选择的贝壳大小 s0 可以不同。而最终 Flute 得到的柠檬数,就是所有小段柠檬数的总和。Flute 想知道,它最多能用这一串贝壳
变出多少柠檬。请你帮忙解决这个问题。

Tag

动态规划,决策单调性,二分

解决思路

首先,我们是可以\(O(n)\)地处理出对于每一个位置上的柠檬,在它之前的与它大小一样的最后的柠檬的位置 ,基于这个,我们便还可以处理出\(S[i]\)表示前i个中与i颜色一样的柠檬的个数。
那么,设F[i]表示前i个柠檬可以得到的最大贝壳数。可以贪心地知道,最后一段中选择的柠檬的大小一定与最后一个的大小相同,因为若不相同,可以把最后一段再分开成其它段,这样答案不会更差,可能会更优。
于是我们可以得到一个这样的转移方程
\[F[i]=max(F[j]+A[i]*(S[i]-S[j]+1)^2)\quad 其中A[i]是i处的大小,j是i前面一个与i同大小的柠檬\]
由于\(S[i]\)都是非负的,所以我们可以发现,当决策点\(j\)不动的时候,随着\(i\)的增大,\((S[i]-S[j]+1)^2\)这个值会增长得越来越快。由于二次函数的性质,S[j]更小的j虽然一开始可能比更大的j劣,但它增长得更快,所以决策点是向左移动的。
所以,我们对每一种大小维护一个单调队列,当队尾的第二个元素的值由于第一个时,就弹出队尾。
但是这样有一个问题,对于\(a < b < c\),若开始的时候c比b更优,c比a更优,但随着i慢慢向后,a会超过c,b也会超过c;当b超过c的时候,我们会弹出c,但此时a可能已经比b更优了,我们却不知道,此时就会使得答案不是最优解。
怎么办呢?我们知道若a超过i1的时间早于b超过i1的时间,那么对于任何i1 < i2,a超过i2的时间也是早于b超过i2的,所以对于队尾的元素a,b,设a < b,若a超过b的时间早于b超过当前的i的时间,则说明b是可以弹掉的。
至于怎么求一个函数超过另一个函数的时间呢?二分就好了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100;
const int maxNum=maxN;
const int inf=2147483647;

int n;
int Num[maxN],Last[maxN];
vector<int> Queue[maxNum];
ll F[maxN],S[maxN];

int Beyond(int u,int v);
ll Calc(int p,ll key);

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>Num[i];
    for (int i=1;i<=n;i++){
        S[i]=S[Last[Num[i]]]+1;Last[Num[i]]=i;//预处理S数组
    }
    ll Ans=0;
    for (int i=1;i<=n;i++)
    {
        int id=Num[i];
        while ((Queue[id].size()>=2)&&(Beyond(Queue[id][Queue[id].size()-2],Queue[id][Queue[id].size()-1])<=Beyond(Queue[id][Queue[id].size()-1],i))) Queue[id].pop_back();//弹队尾
        Queue[id].push_back(i);
        while ((Queue[id].size()>=2)&&(Beyond(Queue[id][Queue[id].size()-2],Queue[id][Queue[id].size()-1])<=S[i])) Queue[id].pop_back();//取最优解
        F[i]=Calc(Queue[id][Queue[id].size()-1],S[i]-S[Queue[id][Queue[id].size()-1]]+1ll);
        Ans=max(Ans,F[i]);
    }
    cout<<Ans<<endl;
    return 0;
}

int Beyond(int u,int v)//二分出u超过v的时间
{
    int l=1,r=n;
    int Ret=n+1;
    do
    {
        int mid=(l+r)>>1;
        if (Calc(u,mid-S[u]+1ll)>=Calc(v,mid-S[v]+1ll)) Ret=mid,r=mid-1;
        else l=mid+1;
    }
    while (l<=r);
    return Ret;
}

ll Calc(int p,ll key)
{
    return F[p-1]+(ll)Num[p]*key*key;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4709][JSOI2011]柠檬 (动态规划,决策单调性,二分)


HNCJ OIer