洛谷 P3648 [APIO2014]序列分割（斜率优化dp）

题目链接：P3648 [APIO2014]序列分割

题解:

这题中我们需要使用二维数组$dp[i][j]$表示当前考虑前$i$个点，分割了$j$次,且最后一次分割位置为$i$的最大得分，因为数据$n\le$ 100000, $k\le$ 200,因此$n\ast k\le 1e7$，此时我们就需要使用滚动数组来优化内存。
首先使用$pre[i]$表示前$i$个数的和，我们可以很容易就推出状态转移方程
$dp[i][j]=max(dp[j][j-1]+(pre[i]-pre[j])\ast (pre[n]-pre[i])),j\le i$
如果做过我上一篇博客的题，那么很明显我们可以发现这个状态转移方程可以进行斜率优化，考虑当前为第$t$次分割且$j\le k\le i$,$k$比$j$优的时满足：
$dp[j][t-1]+(pre[i]-pre[j])\ast (pre[n]-pre[i])\le dp[k][t-1]+(pre[i]-pre[k])\ast (pre[n]-pre[i])$
化简后为：
$pre[n]-pre[i]\le (dp[k][t-1]-dp[j][t-1])/(pre[k]-pre[j])$
使用单调队列维护凸包即可。（注意，因为求斜率时可能$pre[j]=pre[k]$,所以要特判一下，直接返回$-1e18$）

具体细节见代码和注释：

ll dp[N][4];//滚动数组dp[i][j]表示前i个点分割j次的，且最后一次在位置j的得分
ll a[N],pre[N];
int q[N];
long double get_k(int t,int j,int k){
	if(pre[k]==pre[j]){
		return -inf;
	}
	return 1.0*(dp[k][t%3]-dp[j][t%3])/(pre[k]-pre[j]);
}
vector<int>way[210];//存路径
int main(){
/*cout<<setiosflags(ios::fixed)<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（不含整数部分）*/
/*cout<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（含整数部分）*/
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
	}
	for(int t=1;t<=k;t++){//枚举分割次数
		int l=1,r=1;
		q[r]=0;
		for(int i=1;i<=n;i++){
			while(l<r&&get_k(t-1,q[l],q[l+1])>=(pre[n]-pre[i])){
				l++;
			}
			dp[i][t%3]=dp[q[l]][(t-1+3)%3]+(pre[i]-pre[q[l]])*(pre[n]-pre[i]);
			way[t].emplace_back(q[l]);
			while(l<r&&get_k(t-1,q[r-1],q[r])<=get_k(t-1,q[r],i)){
				r--;
			}
			q[++r]=i;
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++){
		if(dp[i][k%3]>dp[ans][k%3]){
			ans=i;
		}
	}
	cout<<dp[ans][k%3]<<endl;
	for(int i=k;i>1;i--){
		cout<<ans<<" ";
		ans=way[i][ans-1];
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49