Description
Flute 很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 N (1 ≤ N
≤ 100,000) 只，按顺序串在树枝上。为了方便，我们从左到右给贝壳编号 1..N。每只贝壳的大小不一定相同，
贝壳 i 的大小为 si(1 ≤ si ≤10,000)。变柠檬的魔法要求，Flute 每次从树枝一端取下一小段连续的贝壳，并
选择一种贝壳的大小 s0。如果 这一小段贝壳中 大小为 s0 的贝壳有 t 只，那么魔法可以把这一小段贝壳变成 s
0t^2 只柠檬。Flute 可以取任意多次贝壳，直到树枝上的贝壳被全部取完。各个小段中，Flute 选择的贝壳大小 s
0 可以不同。而最终 Flute 得到的柠檬数，就是所有小段柠檬数的总和。Flute 想知道，它最多能用这一串贝壳
变出多少柠檬。请你帮忙解决这个问题。
Solution
首先猜一个结论:每一段的开头和结尾的颜色是一样的,且这一段选择的颜色一定就是开头的颜色
这样就可以得到DP式 \(f[i]=min(f[j-1]+a[i]*(s[i]-s[j]+1)^2),a[i]==a[j]\)
这个东西是有决策单调性的,因为平方函数增长快,所以前面位置的一定到后面会越来越大
下面的每一个数字是下标的话,大致就是这样分布的:
333222111111
我们每一次判断一个决策能否被另一个决策覆盖,如果能我们就弹掉这个元素,用一个单调栈维护就行了
找分界点可以用二分求出,也可以直接压在栈里,减少常数
#include<bits/stdc++.h>#define p (S[o].size()-1)#define q (S[o].size()-2)using namespace std;typedef long long ll;const int N=1e5+10;int n,a[N],id[N],c[N];ll f[N];vector<int>S[N/10];inline ll g(int x,int y){return f[x-1]+1ll*a[x]*y*y;}inline int k(int x,int y){ ???int l=1,r=n,mid,ret=n+1; ???while(l<=r){ ???????mid=(l+r)>>1; ???????if(g(x,mid-id[x]+1)>=g(y,mid-id[y]+1))ret=mid,l=mid+1; ???????else r=mid-1; ???} ???return ret;}int main(){ ?freopen("pp.in","r",stdin); ?freopen("pp.out","w",stdout); ?scanf("%d",&n); ?for(int i=1,o;i<=n;i++){ ?????scanf("%d",&a[i]);o=a[i];id[i]=++c[o]; ?????while(S[o].size()>=2 && k(S[o][p],S[o][q])<=k(i,S[o][p]))S[o].pop_back(); ?????S[o].push_back(i); ?????while(S[o].size()>=2 && k(S[o][p],S[o][q])<id[i])S[o].pop_back(); ?????f[i]=g(S[o][p],c[o]-id[S[o][p]]+1); ?} ?cout<<f[n]<<endl; ?return 0;}bzoj 4709: [Jsoi2011]柠檬
原文地址：https://www.cnblogs.com/Yuzao/p/8661253.html