重修斜率优化 Dp

2022/8/15 23:26:45

编程Tag： min define tail DP 2S 单调斜率重修

本文主要是介绍重修斜率优化 Dp，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

斜率单调暴力移指针

斜率不单调二分找答案

\(x\) 坐标单调开单调队列

\(x\) 坐标不单调开平衡树 / cdq分治

P4072 [SDOI2016]征途

我们要求方差最小，而总和不变，等价于要每天走的路程平方和最小。

设 \(s(i)\) 表示前 \(i\) 段路的距离总和。

首先我们有一个 naive 的 \(O(n^3)\) DP：

设 \(f(i,j)\) 表示走完前 \(n\) 段，用了 \(j\) 天的最小平方和。

\[f(i,j)=\min_{k=0}^i f(k,j-1)+(s(i)-s(k))^2 \]

发现后面的 \((s(i)-s(k))^2\) 明显就是斜率优化 DP，我们转化一下形式：

\[\begin{aligned} f_j(i)&=\min_{k=0}^i f_{j-1}(k)+s^2(i)+s^2(k)-2s(i)s(k) \\&=s^2(i)+\min_{k=0}^i f_{j-1}(k)+s^2(k)-2s(i)s(k) \end{aligned} \]

若转移至 \(f_j(i)\) 时 \(k_0\) 不比 \(k\) 劣，则有

\[f_{j-1}(k_0)+s(k_0)^2-2s(i)s(k_0)\le f_{j-1}(k)+s^2(k)-2s(i)s(k) \]

将 \(i\) 有关移到一侧:

\[\frac{(f_{j-1}(k_0)+s(k_0)^2)-(f_{j-1}(k)+s^2(k))}{s(k_0)-s(k)}\le 2s(i) \]

不妨设 \(g(k)=f_{j-1}(k)+s^2(k)\)，则

\[\frac{g(k_0)-g(k)}{s(k_0)-s(k)}\le 2s(i) \]

发现左边就是 \((s(k_0),g(k_0)),(s(k),g(k))\) 两点间的斜率。

所以说，我们对于每一次 \(j-1\to j\)，都进行斜率优化，复杂度 \(O(n^2)\)。

（\(x\) 坐标单调开单调队列）

点击查看代码

//We'll be counting stars.
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define mkp make_pair
#define pb emplace_back
#define For(i,j,k) for(int i=(j),i##_=(k);i<=i##_;i++)
#define Rof(i,j,k) for(int i=(j),i##_=(k);i>=i##_;i--)
#define ckmx(a,b) a=max(a,b)
#define ckmn(a,b) a=min(a,b)
#define debug(...) cerr<<"#"<<__LINE__<<": "<<__VA_ARGS__<<endl
#define int long long
#define db double
#define N 3003 
int n,m,a[N],f[2][N],q[N],head,tail;
inline int pw(int x){ return x*x; }
db SL(bool o,int x,int y){//slope
	return 1.*((f[o][y]+pw(a[y]))-(f[o][x]+pw(a[x])))/(a[y]-a[x]);
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);
	cin>>n>>m;
	For(i,1,n) cin>>a[i];
	For(i,2,n) a[i]+=a[i-1];
	For(i,1,n) f[1][i]=pw(a[i]);
	bool o;
	int tmp;
	For(i,2,m){
		o=(i&1)^1;
		head=1,tail=0;
		For(j,1,n){
			while(head<tail && SL(o,q[head],q[head+1])<2*a[j])
				head++;
			tmp=q[head];
			f[o^1][j]=f[o][tmp]+pw(a[j]-a[tmp]);
			while(head<tail && SL(o,q[tail-1],q[tail])>=SL(o,q[tail],j))
				tail--;
			q[++tail]=j;
		}
	}
	tmp=f[m&1][n];
	cout<<m*tmp-pw(a[n]);
return 0;}

这篇关于重修斜率优化 Dp的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

重修 斜率优化 Dp

P4072 [SDOI2016]征途

相关编程文章

重修斜率优化 Dp