两道斜率优化的涨姿势的题目
洛谷CF311B Cats Transport
分析
没什么好分析的和上面一样公式套取就好了（套个鬼哦）。这道题最关键的就是教会了我们，消除非关键因素的影响是多么重要
咳咳。首先你要分析怎么把这道题硬设计出 dp 状态。那么我们来看看，其实路程对于问题的影响并不显得有多么重要，于是我们可以考虑消除这个影响。
如何消除？题目中说，饲养员（说好的铲屎官…）到达猫的位置所需时间就是距离 $X_{i}$，那么其实猫在 $T_{i}$ 的时间开始等待，而饲养员出发时间对于我们要求的答案是没有影响的（何况题目中说了饲养员出发时间可以为负数），
那么我们可以让猫开始等待的时间 $T_{i}$ 减去路程的影响 $X_{i}$ （感性理解一下），然后我们再对减完 $X_{i}$ 的 $T_{i}$ 排一下序就好了。
这里如何解释？emmm…思考一下，一个饲养员出发必然是会接回所有正在等待的猫对吧（猫不可能给下一个人接，那样不会更优，而上一个人能接回去早接回去了）
咳咳…那么这个饲养员能接到哪些猫呢？当然是 $T-X$（等待开始时间减去路程） 小于等于饲养员出发时间的所有猫咯！于是解释完毕。
排完序后，可以看出我们要接到第 i 只猫的话，它前面的猫我们都可以接到（因为在这只猫之前的猫早就开始等待了）。
于是这道题就变成了分割序列…（切 p 刀，但是注意这里是最多切 p 刀，不一定切完，有的饲养员可以不动的嘛）。
咳咳，但是转移方程是不一样的：$ F_{i} = F_{j} + (T_{i}-T_{i-1}) * (i-j) – (T_{i}-T_{j}) $ （T 是上文中 $T-X$ 的前缀和数组）
那么这个表达式原来的样子是：$ F_{i} = MIN{ F_{j} + \sum_{k=j}^{i} ( t_{i}-t_{k} ) }$ （这里的 t 是上文中的 $T-X$ 数组）
然后我们就非常愉快的 ctrl+C 、 ctrl+V 将之前打好的序列分割板子弄了下来开始了新一轮的斜率优化。
代码
1 //by Judge
2 #include<algorithm>
3 #include<iostream>
4 #include<cstdio>
5 #define ll long long
6 using namespace std;
7 const int M=1e5+111;
8 const ll inf=1e16+7;
9 #ifdef ONLINE_JUDGE
10 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
11 #endif
12 char buf[1<<21],*p1=buf,*p2=buf;
13 inline int read(){
14 int x=0,f=1; char c=getchar();
15 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
16 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
17 }
18 ll n,m,p,ans=inf,d[M],a[M],g[M],f[M],q[M],head,tail;
19 inline double Y(int i){ return g[i]+a[i]; }
20 inline double X(int i){ return i; }
21 inline double Rate(ll i,ll j){ return (Y(j)-Y(i))/(X(j)-X(i)); }
22 signed main(){
23 n=read(),m=read(),p=read();
24 for(int i=2;i<=n;++i) d[i]=d[i-1]+read();
25 for(int i=1,x,y;i<=m;++i) x=read(),y=read(),a[i]=y-d[x],g[i]=inf;
26 sort(a+1,a+m+1); for(int i=2;i<=m;++i) a[i]+=a[i-1];
27 for(int k=1,i;k<=p;++k){
28 head=tail=0;
29 for(i=1;i<=m;++i){
30 while(head<tail && Rate(q[head+1],q[head])<=a[i]-a[i-1]) ++head;
31 f[i]=g[q[head]]+(a[i]-a[i-1])*(i-q[head])-a[i]+a[q[head]];
32 while(head<tail && Rate(q[tail-1],q[tail])>=Rate(q[tail],i)) --tail; q[++tail]=i;
33 } swap(f,g); ans=min(ans,g[m]);
34 } printf("%lld\n",ans); return 0;
35 }
BinamotoOJ P4709: [Jsoi2011]柠檬
分析
这题就是斜率优化裸题啊！ 这道题非常值得一做，因为它深刻的告诉了我们，斜率优化可以用单调栈维护！
首先这题就是让我们吧一个序列分成若干份，然后根据公式计算最大值（注意是最大值，维护折线上凸性）
我们可以非常轻松的看出我们要取的一段区间的左右端点必然是相同的颜色，且我们选择的颜色就是左右端点的颜色。
（我们每一段只能选一种颜色，那么如果左右端点不同，我们完全可以将与选择的颜色不同的那一端隔离出来分到另一段区间里，那样更优）
于是我们在读入时维护一个 las 指针，指向当前颜色上一次出现的位置，同时记录每个点之前与该点颜色相同的点有多少个（用 S 数组记录）。
然后我们将所有颜色第一次出现时的位置压入单调栈，接着就可以开始 dp 了。
那么 dp 转移式就是 ： $$ f[i] = f[j-1] + (s[i]-s[j]+1)*a[i] $$ （其中 i 、j 位置的贝壳颜色相同）
斜率式就是： $$ f[i] + 2*a[i]*s[i]*s[j] = f[j-1] + a[i]*s[j]^{2} – 2*a[i]*s[j] + 2*a[i]*s[i]+a[i]*s[i]^{2}+a[i] $$
$$ X(i)= s[j] , K=2*a[i]*s[i] $$
$$ Y(i)= f[j-1] + a[i]*s[j]^{2} – 2*a[i]*s[j] $$
代码
1 //by Judge
2 #include<iostream>
3 #include<cstdio>
4 #include<queue>
5 #define ll long long
6 using namespace std;
7 const int M=1e5+111;
8 //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
9 char buf[1<<21],*p1=buf,*p2=buf;
10 inline int read(){
11 int x=0,f=1; char c=getchar();
12 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
13 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
14 }
15 ll n,ans,las[M],a[M],s[M],f[M],top[M]; vector<int> q[M];
16 inline long double X(int i){ return s[i]; }
17 inline long double Y(int i){ return f[i-1]+a[i]*s[i]*(s[i]-2); }
18 inline long double Rate(ll i,ll j){ return (Y(j)-Y(i))/(X(j)-X(i)); }
19 signed main(){
20 n=read(); ll p,x,y;
21 for(int i=1;i<=n;++i) a[i]=read(),s[i]=s[las[a[i]]]+1,las[a[i]]=i;;
22 for(int i=1;i<=n;++i) if(las[a[i]]) q[a[i]].push_back(i),las[a[i]]=0;
23 for(int i=1;i<=n;++i){ p=a[i];
24 while(top[p]>1 && Rate(q[p][top[p]-1],q[p][top[p]])<=Rate(q[p][top[p]],i)) --top[p],q[p].pop_back();
25 ++top[p],q[p].push_back(i);
26 while(top[p]>1 && Rate(q[p][top[p]-1],q[p][top[p]])<=2*p*s[i]) --top[p],q[p].pop_back();
27 f[i]=f[q[p][top[p]]-1]+(s[i]-s[q[p][top[p]]]+1)*(s[i]-s[q[p][top[p]]]+1)*p;
28 } printf("%lld\n",f[n]); return 0;
29 }