斜率优化
斜率优化
直接看例题
例题：P3195
解析
转移方程很简单：
这里\(f[i]\)表示前\(i\)个物品的最优代价。\(a\)为\(c\)（如题目）的前缀和。
\[a[i]=\sum_{j=1}^i c[j] \\ f[i]=\min(f[j]+(a[i]-a[j]+i-j-1-L)^2) \]令\(g[i][j]\)表示表示在j处分段，前面按最优方案，后面直到i全部放到1个盒子里的代价。所以：
\[f[i]=min(g[i][j])\\ g[i][j]=f[j]+(a[i]-a[j]+i-j-1-L)^2 \]由于\(a[i],a[j],i,i,L,f[j]\)都为已知量，换元来简化计算。
\[b[i]=a[i]+i\\ c[i]=a[i]+i+1+L \]现在式子就很好看了
\[\begin{aligned} &g[i][j]=f[j]+(b[i]-c[j])^2\\ &g[i][j]=f[j]+b[i]^2+c[j]^2-2b[i]c[j]\\ &2b[i]c[j]+g[i][j]-b[i]^2=f[j]+c[j]^2 \end{aligned} \]还记得\(b[i],f[j],c[j]\)都是常数吗，既然都是常数，那么可以把这个式子理解成\(2b[i]\)为\(k\)（斜率），\(g[i][j]-b[i]^2\)为\(b\)（截距），经过定点\((c[j],f[j]+c[j]^2)\)的一次函数！
斜率一定，且经过定点，那么\(g[i][j]=截距+b[i]\)
这样我们就可以通过图像来分析性质了！
从hhz6830975的题解里盗来的图（侵删）
由于我们要找最小的\(g[i][j]\)，所以只有下凸包> 里的点可能有贡献，令\(P[i]\)表式下凸包里，从左到右第i个点。根据凸包的性质，\(P[i],P[i+1]\)的斜率随i递增，那么真正用来转移的点（使截距最大的点）就是第一个让\(P[i],P[i+1]的斜率>=2b[i]\)的点。
总结
所有转移方程可以转化成定斜率的一次函数即具有决策单调性的DP都可以考虑使用斜率优化。
这样的转移方程大多形如：
\[f[i]=\min(\max)(f[j]+(a[i]-b[j])^2)\\ \]大概的推导就是把下标为\(i\)的和有\(i\)有\(j\)的扔一边，其他扔对面
\[f[i]=f[j]+a[i]^2+b[j]^2-2a[i]b[j]\\ 2a[i]b[i]+f[i]-a[i]^2=b[j]^2+f[j] \]始终记住a[i]，b[j]是可以通过下标直接计算得出的常数。
实现
用单调队列的思想实现，注意不同变量的不同单调性。
#include
using namespace std;
#define ll long long
const int MM=55000;
ll n,L,c[MM],f[MM],a[MM],q[MM],h,t;
double b(int x)
{
return a[x]+x+L+1;
}
double xl(int x,int y)
{
return (f[x]+b(x)*b(x)-f[y]-b(y)*b(y))/(b(x)-b(y));
}
int main()
{
cin>>n>>L;
for(int i=1;i<=n;i++)
cin>>a[i],a[i]+=a[i-1];
h=t=1;
for(int i=1;i<=n;i++)
{
while(hxl(i,q[t-1]))--t;
q[++t]=i;
}
cout< 再来道例题
P2900
\(P_{ix}\)表示第i块的长\(P_{iy}\)表示第i块地的宽，如果存在\(P_{jx}>P_{ix}\)且\(Pjy>Piy\)，那么只要在买含第j块地的一组时顺便把第i块地买了就好，所以第i块地对答案不会有贡献。
考虑所有有贡献的地，将这些地按长升序排序，那么宽一定是降序的。
分析到这可以开始DP了。
\(f[i]\)表示前买前i块地的代价转移方程十分显然：
\[f[i]=min(f[j]+y[j+1]*x[i]) \]\(O(n^2)\)肯定过不了，考虑斜率优化。
稍微推下式子:
\[-y[j+1]*x[i]+f[i]=f[j] \]\(x[i]\)为斜率，过\((-y[j+1],f[j])\)
这次是自己画的图：
如图，还是一样的维护凸包的过程，但要注意最开始在单调栈插入一个\(0\)即图中\((y[1],0)\)的点，代表把前\(i\)个一次性买了。
实现
#include
using namespace std;
#define ll long long
const int MM=50004;
struct orzzy
{
int x,y;
}p[MM];
bool cmp(orzzy a,orzzy b)
{
if(a.y==b.y)
return a.x>n;
for(int i=1;i<=n;i++)
cin>>p[i].x>>p[i].y;
sort(p+1,p+n+1,cmp);
for(int i=n;i>=1;i--)
if(p[i].x>tmp)
tmp=p[i].x,x[++tot]=p[i].x,y[tot]=p[i].y;
n=tot;
h=t=1;
for(int i=1;i<=n;i++)
{
while(hxl(q[t-1],i))t--;
q[++t]=i;
}
cout<