【洛谷】P5504 [JSOI2011] 柠檬（决策单调性优化dp）
原题链接
题意
Flute 很喜欢柠檬。
它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。
贝壳一共有 \(N\) 只，按顺序串在树枝上。
为了方便，我们从左到右给贝壳编号 \(1..N\)。
每只贝壳的大小不一定相同，贝壳 \(i\) 的大小为 \(s_i\)。
变柠檬的魔法要求，Flute 每次从树枝一端取下一小段连续的贝壳，并选择一种贝壳的大小 \(s_0\)。
如果这一小段贝壳中大小为 \(s_0\) 的贝壳有 \(t\) 只，那么魔法可以把这一小段贝壳变成 \(s_0t^2\) 只柠檬。
Flute 可以取任意多次贝壳，直到树枝上的贝壳被全部取完。
各个小段中，Flute 选择的贝壳大小 \(s_0\) 可以不同。
而最终 Flute 得到的柠檬数，就是所有小段柠檬数的总和。
Flute 想知道，它最多能用这一串贝壳变出多少柠檬。
数据范围
\(1≤N≤10^5\),\(1≤s_i≤10^4\)
思路
设 \(f[i]\) 表示前 \(i\) 个贝壳得到的最大柠檬数，仔细理解题意，可以发现每次 \(f[i]\) 的决策点 \(j\) 一定满足 \(s_i=s_j\)，即每一段连续的贝壳两端大小一定相同。这是因为如果不相同，那么还不如让一端的单独成一段。
得到状态转移方程：
\(f[i]=\min_{s[i]=s[j]}(f[j-1]+s[j]*(cnt[i]-cnt[j]+1)^2)\)。
注意到 \(s[j]*(cnt[i]-cnt[j]+1)^2\) 的大小是同时与 \(i,j\) 的取值相关，可以考虑斜率优化。这里主要介绍另一种优化方式——决策单调性。
把 \(f[j-1]+s[i]*(cnt[i]-cnt[j]+1)^2\) 中与 \(j\) 有关的数组看成常量，把 \(i\) 看成是因变量，那么整个式子就是一个关于 \(i\) 的二次函数。那么单调性就很明显了。因为后来的决策点 \(f[j-1]\) 大，但是 \(cnt[i]-cnt[j]+1\) 的值小，如下图所示：
所谓单调性，实际上就是对于两个决策点，存在一个数 \(k\)，满足当 \(i < k\) 时第一个决策点更优，当 \(i \geq k\) 时第二个决策点更优。在本题中，越大的决策点，使用的范围越靠前。因此可以将所有的决策点放入一个单调栈中，维护的就是 \(k\) 单调递增的决策点，意思是在 \(k\) 之前栈上面的决策点更优，在 \(k\) 之后栈下面的决策点更优。此时栈顶就是当前最优的点。
考虑在入栈时什么时候需要出栈，如下图
可以发现，在这种情况下最优决策点永远也轮不到 top。归纳一下，就是当 \(k_{top,i} \geq k_{top-1,top}\) 时，就可以将 top 出栈。
如果当前栈顶的决策区间不包含 \(i\)，即 \(k_{top-1,top}
总的时间复杂度就是 \(O(n \log n)\)，相较于斜率优化的 \(O(n)\)。时间复杂度和思维难度都更高。但是在一些特殊的情况下，斜率优化是不适用的，那么就需要用到决策单调性了。
决策单调性的维护方法很多。遇到具体题目可以具体分析。
code：
#include
#include
#include
using namespace std;
const int N=1e5+10;
#define LL long long
LL f[N],s[N],c[N];int n,cnt[N];
vectorq[N];
#define t(i) q[i][q[i].size()-1]
#define tt(i) q[i][q[i].size()-2]
LL get(int j,int t){return f[j-1]+1ll*c[j]*t*t;}
int calc(int x,int y)//这里二分的是第二个函数第一个适用的位置
{
int l=1,r=n;
while(l>1;
if(get(x,mid-s[x]+1)>=get(y,mid-s[y]+1)) r=mid;
else l=mid+1;
}
return get(x,r-s[x]+1)>=get(y,r-s[y]+1)?r:n+1;
}
int main()
{
scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&c[i]),s[i]=++cnt[c[i]];
for(int i=1;i<=n;i++)
{
while(q[c[i]].size()>1&&calc(tt(c[i]),t(c[i]))<=calc(t(c[i]),i)) q[c[i]].pop_back();
q[c[i]].push_back(i);
while(q[c[i]].size()>1&&calc(tt(c[i]),t(c[i]))<=s[i]) q[c[i]].pop_back();
f[i]=get(t(c[i]),s[i]-s[t(c[i])]+1);
}
printf("%lld\n",f[n]);
return 0;
}```