参考资料：
李煜东《算法竞赛进阶指南》
斜率优化
形如：
(f[i] = min{f[j]+val(i,j)})的dp，多项式(val(i,j))包含(i,j)的乘积项
引入一个例题：
(dp[i] = min{dp[j] + (sum[i] + i - sum[j] - j-L-1)^2}(j < i))
定义：(a[i]=sum[i]+i,b[i]=sum[i]+i+L+1)
则
将(b[j])看作x，(dp[j]+b[j]^2)看作y
那么这个式子就是一个(k=2*a[i])的直线
那么我们要最小化这个过((b[j],dp[j]+b[j]^2))的直线的(b)值
根据定义，(a[i])单调递增，那么直线的斜率越来越大
我们可以用单调队列维护下凸壳，不断用(a[i])去切这个凸包
习题：
wqs二分/带权二分/凸优化
解决n个东西恰好选m个的最优问题
普通dp方法一般都是(O(nm))
wqs二分可以优化成(O(nlogW))
引入例题：
有n个物品，每个物品有一个价值，
问：选m个物品可以获得的最大价值。
这显然可以贪心，但是我们为了引出wqs二分，我们想dp做法
(f[i][j]=max(f[i-1][j-1]+val[i],f[i-1][j]))
考虑如果没有m的限制，那么dp式子长这样
(f[i]=f[i-1]+max(v[i],0))
wqs二分又称带权二分
那么我们二分这个带权x
给每个物品价值增加x
显然x越大，我们会选的东西不会变少
如果选的个数大于m，那么x要减小，否则增大
最后(ans=f[n]-x*m)
整数二分x可能会有些精度问题，最好是写实数二分
update:
(wqs)二分的本质是求一个凸函数某个位置的值
但是这有时候并不是很好求。我们转化成用一条斜率为(mid)的直线去切这个函数。
关于整数二分的问题，对于一个切不到刚好选出(m)个的函数，那么显然存在多个相同的，
例如上述的贪心(5,3,3)中选(2)个
如果(mid=3)，则变成(2,0,0)选一个
如果(mid=2)，则变成(3,1,1)选三个
这个时候我们用(mid=3)作为答案是对想想为什么?
习题：
四边形不等式优化
这个东西比较难，看不懂的可以记住结论。（证明由于篇幅过长，有兴趣的可以去查找一下资料）
设(w(x,y))是定义在整数集合的二元函数。若对于定义域上的任意整数(a,b,c,d)，其中(aleq b leq c leq d)，都有(w(a,d)+w(b,c)≥w(a,c)+w(b,d))成立，则称函数(w)满足四边形不等式。
定理（四边形不等式的另一种定义）：对于定义域上任意整数(a,b)，其中(a<b)，都有(w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1))成立，则函数满足四边形不等式。
一维线性dp的四边形不等式优化
形如：(f[i]=min{f[j]+val(j,i)})的dp，记(p[i])为令(f[i])取到最小值的j的值，即(p[i])是(f[i])的最优决策。若(p)在([1,N])上单调不减，则称(f)具有决策单调性
定理（决策单调性）：在上述dp中，若(val)满足四边形不等式，则(f)满足决策单调性。
那么，当(F)有决策单调性时，我们可以把复杂度降低到(O(nlogn))
考虑维护(p)数组。最初(p)数组全部为0。在(i)循环进行的任意时刻，根据(p[i])的单调性，情况应该如下图所示：
(p:[j1,j1,j2,j3,j3,j3,j4,j4,j5,j5,j5]) ((j1<j2<j3<j4<j5))
当求出一个新的(f[i])时，我们应该考虑(i)可以作为哪些(F[i'](i'>i))的最优决策。根据决策单调性，最终我们会找到一个位置，在该位置之前，p数组原来的决策比i好，之后的比i差。这个位置可以二分求得。
怎么修改？
直接修改数组效率肯定不行，我们可以建立一个队列保存三元组((j,l,r))，(j)表示决策，(l,r)表示 (p[ l-r ]) 值都为 (j)
然后像单调队列一样维护即可。
例题：诗人小G
按照上面的模拟即可，注意用long double（精度高） 代替long long。
#include<bits/stdc++.h>
#define LL long long
#define RG register
using namespace std;
template<class T> inline void read(T &x) {
x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
x = f ? -x : x;
return ;
}
template<class T> inline void write(T x) {
if (!x) {putchar(48);return ;}
if (x < 0) x = -x, putchar('-');
int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
#define ld long double
const int N = 100010;
int n, L, P;
ld sum[N], f[N];
char str[N][35];
ld fpow(ld a, int b) {
ld res = 1;
for (; b; b >>= 1, a = a * a) if (b & 1) res = res * a;
return res;
}
ld getans(int l, int r) {
return f[l] + fpow(abs(sum[r] - sum[l] + (r - l - 1) - L), P);
}
struct node {
int j, l, r;
} q[N];
int find(int l, int r, int j, int i) {
int ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
getans(j, mid) >= getans(i, mid) ? ans = mid, r = mid - 1 : l = mid + 1;
}
return ans;
}
int p[N], que[N];
void solve() {
read(n), read(L), read(P);
for (int i = 1; i <= n; i++) {
scanf("%s", str[i]);
sum[i] = sum[i - 1] + (int) strlen(str[i]);
}
int l = 0, r = 0;
q[l] = (node) {0, 1, n};
for (int i = 1; i <= n; i++) {
if (q[l].r < i) l++;
p[i] = q[l].j; q[l].l = i;
f[i] = getans(q[l].j, i);
while (l <= r && getans(q[r].j, q[r].l) >= getans(i, q[r].l)) r--;
if (getans(q[r].j, q[r].r) < getans(i, q[r].r)) { if (q[r].r < n) q[r + 1] = (node) {i, q[r].r + 1, n}, r++; }
else {
int pos = find(q[r].l, q[r].r, q[r].j, i);
q[r].r = pos - 1;
q[++r] = (node) {i, pos, n};
}
}
if (f[n] > 1e18) puts("Too hard to arrange");
else {
printf("%lld
", (LL) f[n]);
int now = n, tot = 0;
while (now) que[++tot] = now, now = p[now];
que[tot + 1] = 0;
for (int i = tot; i; i--) {
for (int j = que[i + 1] + 1; j < que[i]; j++)
printf("%s ", str[j]);
puts(str[que[i]]);
}
}
puts("--------------------");
return ;
}
int main() {
int T;
read(T);
while (T--) solve();
return 0;
}
二维区间DP的四边形不等式优化
区间DP问题
一类区间问题的转移方程：
(f[i][j]=min{f[i][k]+f[k+1][j]+w(i,j)})
定理
在上述方程中，如果(w)满足四边形不等式，且(w(a,d)≥w(b,c)[a≤b≤c≤d])
那么(f)也满足四边形不等式
二维决策单调性
记(p[i][j])为令(f[i][j])取到最小值的(k)值，如果(f)满足四边形不等式，那么对于任意(i<j)，有(p[i][j-1]≤p[i][j]≤p[i+1][j])
例题：[IOI2000]邮局
先写出转移方程：(f[i][j]=min{f[i][j],f[k][j−1]+dis(k+1,i)})
显然这个(dis)满足四边形不等式。
那么这个(f)满足决策点单调性
#include<bits/stdc++.h>
#define LL long long
#define RG register
using namespace std;
template<class T> inline void read(T &x) {
x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
x = f ? -x : x;
return ;
}
template<class T> inline void write(T x) {
if (!x) {putchar(48);return ;}
if (x < 0) x = -x, putchar('-');
int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 3010;
int a[N], n, m, p[N][N], sum[N], f[N][N], w[N][N];
int main() {
read(n), read(m);
for (int i = 1; i <= n; i++) read(a[i]);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++) {
int mid = (i + j) >> 1;
w[i][j] = a[mid] * (mid - i) - (sum[mid - 1] - sum[i - 1]);
w[i][j] += (sum[j] - sum[mid]) - a[mid] * (j - mid);
}
memset(f, 63, sizeof(f));
for (int i = 1; i <= n; i++)
f[i][1] = w[1][i];
for (int j = 2; j <= m; j++) {
p[n + 1][j] = n;
for (int i = n; i >= 1; i--)
for (int k = p[i][j - 1]; k <= p[i + 1][j]; k++)
if (f[i][j] > f[k][j - 1] + w[k + 1][i]) {
f[i][j] = f[k][j - 1] + w[k + 1][i];
p[i][j] = k;
}
}
printf("%lld
", f[n][m]);
return 0;
}