又是优化DP，孩子人都傻了。
什么是决策单调性
如果有\(dp_i=\min\limits_{j\ <\ i}(dp_j+\delta_{j,i})\)
并保证对于\(\forall i,j(i<j)\)，有\(\exists k\)，使得\(\forall pos\in\left[0,k\right],dp_i+\delta_{i,pos}\le dp_j+\delta_{j,pos}\)且\(\forall pos\in(k,n],dp_i+\delta_{i,pos}>dp_j+\delta_{j,pos}\)，则说明决策有单调性。
（不就是说某个位置之前的点用\(i\)转移更优，而之后的点用\(j\)转移更优嘛）
如何判断是否满足决策单调性
1.满足四边形不等式的一定满足决策单调性
\(\text{想起}\left\lceil\text{四边形不等式}\right\rfloor\)：\(\forall p_1\le p_2\le p_3\le p_4\)，有\(\delta_{p_1,p_3}+\delta_{p_2,p_4}\le \delta_{p_1,p_4}+\delta_{p_2,p_3}\)
然后发现\(\text{四边形不等式}\Rightarrow\text{决策单调性}\)，通了反证法。
\[若i<j<k_1<k_2 \]
\[且t(i,k_1)>t(j,k_1) \]
\[t(i,k_2)\le t(j,k_2) \]
\[我们知道 \]
\[w(i,k_1)+w(j,k_2)\le w(i,k_2)+w(j,k_1) \]
\[所以可以得到 \]
\[t(i,k_2)+w(i,k_1)+w(j,k_2)\le w(i,k_2)+w(j,k_1)+t(j,k_2) \]
\[所以有 \]
\[t(i,k_1)\le t(j,k_1) \]
\[与题设相悖 \]
优化吧
1.一层分治
\(\color{skyblue}{P4072\ [SDOI2016]\text{征途}}\)
\(dp_{date,i} = \min\limits_{j=1}^{i-1}(dp_{date-1,j}+(pre_i-pre_j)^2)\)
#include <stdio.h>
#include <string.h>
const int N = 4096;
int n, m;
int a[N];
int dp[N][N];
int date;
int delta(int f,int t) {
return dp[date-1][f]+(a[f]-a[t])*(a[f]-a[t]);
//每一天的状态只与上一天有关;
//其实可以滚动压数组大小;
}
void devide(int l,int r,int L,int R) {
//l~r:目前要求解的区间;
//L~R:解可能产生的区间;
if(l > r)
return;
int mid = (l+r)>>1;
int pos = L, res = 998244353;
for(int i = L;i <= R;++i) {
int del = delta(i,mid);
if(del < res) {
res = del;
pos = i;
}
}//枚举解的区间;
dp[date][mid] = res;
devide(l,mid-1,L,pos);
devide(mid+1,r,pos,R);
//因为一个地点可能负责产生很多数的最优解;
//所以pos不加不减;
}
signed main() {
scanf("%d %d",&n,&m);
for(int i = 1, temp;i <= n;++i) {
scanf("%d",&temp);
a[i] = a[i-1]+temp;
}
memset(dp,0x3f,sizeof(dp));
dp[0][0] = 0;
for(int i = 1;i <= m;++i) {
date++;
devide(1,n,0,n-1);
}
printf("%lld",1ll*dp[m][n]*m-1ll*a[n]*a[n]);
}
2.二层分治
\(\color{skyblue}{P3195 [HNOI2008]\text{玩具装箱}}\)
用到了两层分治的原因是，这个的状态与之前的状态有关，必须先把之前的状态算出来。
\(dp_i=\min\limits_{j=1}^{i-1}(dp_j+(i-(j+1)+pre_i-pre_j-L)^2)\)
#include <stdio.h>
#include <string.h>
#include <bits/stl_algobase.h>
using namespace std;
const int N = 5e4+10;
int n, L;
long long a[N];
long long dp[N];
long long delta(int f,int t) {
return dp[f]+(t-f-1+a[t]-a[f]-L)*(t-f-1+a[t]-a[f]-L);
}
void devide(int l,int r,int L,int R) {
if(l > r)
return;
int mid = (l+r)>>1;
int pos = L;
long long res = 99999999998244353;
//开的要大;
for(int i = L;i <= R;++i) {
long long del = delta(i,mid);
if(del < res) {
res = del;
pos = i;
}
}
dp[mid] = min(dp[mid],res);
devide(l,mid-1,L,pos);
devide(mid+1,r,pos,R);
//几乎一模一样;
}
void solve(int l,int r) {
if(l == r)
return;
int mid = (l+r)>>1;
solve(l,mid);
//先处理前面的;
devide(mid+1,r,l,mid);
solve(mid+1,r);
}
signed main() {
scanf("%d %d",&n,&L);
for(int i = 1, temp;i <= n;++i) {
scanf("%d",&temp);
a[i] = a[i-1]+temp;
}
memset(dp,0x3f,(n+1)*sizeof(long long));
dp[0] = 0;
solve(0,n);
printf("%lld",dp[n]);
}
3.二分栈
#include <stdio.h>
#include <bits/stl_algobase.h>
using namespace std;
const int N = 5e4+10;
long long a[N];
int n, L;
long long dp[N];
long long delta(int f,int t) {
return dp[f]+(t-f-1+a[t]-a[f]-L)*(t-f-1+a[t]-a[f]-L);
}
struct NODE {
int x;
int l, r;
//x:位置;
//l~r:x负责的区间;
NODE () {x = l = r = 0;}
NODE (int _in_a,int _in_b,int _in_c) {
x = _in_a;
l = _in_b, r = _in_c;
}
} que[N];
int head = 1, tail;
signed main() {
scanf("%d %d\n",&n,&L);
for(int i = 1, temp;i <= n;++i) {
scanf("%d",&temp);
a[i] = a[i-1]+temp;
}
que[++tail] = NODE(0,1,n);
for(int i = 1;i <= n;++i) {
while(que[head].r < i)
head++;
dp[i] = delta(que[head].x,i);
while(head <= tail&&delta(que[tail].x,que[tail].l) >= delta(i,que[tail].l))
tail--;
if(head > tail) {
que[++tail] = NODE(i,i+1,n);
continue;
}
int l = max(que[tail].l,i+1), r = que[tail].r;
while(l <= r) {
int mid = (l+r)>>1;
if(delta(que[tail].x,mid) >= delta(i,mid))
r = mid-1;
else
l = mid+1;
}
que[tail].r = r;
if(l <= n)
que[++tail] = NODE(i,l,n);
}
printf("%lld",dp[n]);
}
