斜率优化DP-玩具装箱TOY

简洁的学习
更进一步的学习

小总结

1. 优化目的：在依次计算 $dp\left[j\right]$dp[j]时能快速找到前方最优的 $j$j使得从 $j$j到 $i$i的转移最优；若不优化，整体复杂度应为 $O\left(n^2\right)$O(n2)，优化后为 $O\left(nlogn\right)$O(nlogn)或 $O\left(n\right)$O(n)（在于斜率 $k$k随 $i$i是否单调）
2. 关键：能推出直线方程 $kx+b=y$kx+b=y，其中：
   $b$b：包含当前状态 $dp\left[i\right]$dp[i]以及一些常数(只与 $i$i相关)
   $y$y：由只与 $j$j相关的项组成
   $kx$kx：由包含 $i$i和 $j$j的交叉项组成（其中 $k$k只包含与 $i$i有关的项， $x$x只包含与 $j$j有关的项）
3. 多样性：所推出的 $kx+b=y$kx+b=y方程具有多样性，同一个转移方程可以转化为多种正确的直线方程，例如：
   原转移方程： $dp\left[i\right]=dp\left[j\right]+\left(s\right[i]-s[j]-L{)}^2$dp[i]=dp[j]+(s[i]−s[j]−L)2
   直线方程 $1$1： $2\ast s\left[i\right]\ast \left(s\right[j]+L)+dp\left[i\right]-s[i{]}^2=dp[j]+(s\left[j\right]+L{)}^2$2∗s[i]∗(s[j]+L)+dp[i]−s[i]2=dp[j]+(s[j]+L)2
   直线方程 $2$2： $2\ast s\left[i\right]\ast s\left[j\right]+dp\left[i\right]-s[i{]}^2+2\ast s[i]\ast L-L^2=dp[j]+s[j{]}^2+2\ast s\left[j\right]\ast L$2∗s[i]∗s[j]+dp[i]−s[i]2+2∗s[i]∗L−L2=dp[j]+s[j]2+2∗s[j]∗L
4. 算法三大核心：
   1. 斜率函数slope：用直线方程中的 $x$x和 $y$y表达式计算 $x1,y1,x2,y2$x1,y1,x2,y2，求出斜率(double)
   2. 单调队列中寻找最优点：注意若 $k\left[i\right]$k[i]能保证单调，则可进行head++的操作；否则用二分
   3. 将当前状态插入单调队列：维护一个凸包

玩具装箱

题意： 给定每个物品长度，同时打包一些连续的物品会有代价，求打包所有的物品的最小花费

思路：写出转移方程，去掉 $min$min，然后将转移方程化成直线方程（化简过程使用了一些简化方程的手法，细节参见其他博客），注意本题要用long long或者double

如下代码所用的直线方程为： $2\ast s\left[i\right]\ast \left(s\right[j]+L)+dp\left[i\right]-s[i{]}^2=dp[j]+(s\left[j\right]+L{)}^2$2∗s[i]∗(s[j]+L)+dp[i]−s[i]2=dp[j]+(s[j]+L)2

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<ll,int> pr;
inline ll read() {ll x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
 
const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

ll N, L;
ll s[maxn], q[maxn];
ll dp[maxn];

inline double slope(int i, int j) {
	ll x1=s[i]+L, x2=s[j]+L;
	ll y1=dp[i]+(s[i]+L)*(s[i]+L);
	ll y2=dp[j]+(s[j]+L)*(s[j]+L);
	return double(y2-y1)/(x2-x1);
}

int main() {
    //ios::sync_with_stdio(false);
    N=read(), L=read()+1; //L+1为了简化方程
	for(int i=1; i<=N; ++i) s[i]=read(), s[i]+=s[i-1]; //前缀和
	for(int i=1; i<=N; ++i) s[i]+=i; //s[i]+=i也为了简化方程
	int head=0, tail=0;
	for(int i=1; i<=N; ++i) {
		while(head<tail&&slope(q[head],q[head+1])-eps<=2*s[i]) head++; //找最优转移点
		dp[i]=dp[q[head]]+(s[i]-s[q[head]]-L)*(s[i]-s[q[head]]-L);
		while(head<tail&&slope(q[tail-1],i)<slope(q[tail-1],q[tail])) tail--; //将此点插入队列，并维护一个下凸包
		q[++tail]=i;
	}
	printf("%lld\n", dp[N]);
}