DP, 决策单调性, 斜率优化

BZOJ 3675: [Apio2014]序列分割

链接

题意

小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列,小H需要重复k次以下的步骤:
1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列);
2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得k轮之后,小H的总得分最大。

输入

输入第一行包含两个整数n,k ($ k+1≤n $)。
第二行包含n个非负整数a1,a2,…,an($ 0≤ai≤10^4 $),表示一开始小H得到的序列。

输出

输出第一行包含一个整数,为小H可以得到的最大分数。

样例输入

7 3 
4 1 3 4 0 2 3 

样例输出

108

我们首先可以发现交换切割顺序不会影响答案
然后可以得到式子
令$f_{i,k}$表示在取到第i个数时切割k次的最大分数
则 $ f_{i,k}=max\{f_{j,k-1} + sum_{j+1,i} \times sum_{i+1,n} \} $
($sum_{i,k}$ 表示 $\sum^{k}_{j=i}a_j$ )
令$s_i= \sum^{i}_{j=1}a_j$
对于一个固定的k, 令$g_i=f_{i,k-1}$, 则$f_{i,k}=max\{g_j + (s_i – s_j) \times (s_n – s_i)\}$
化简得
$$f_{i,k}=max\{g_j – s_i^2 + s_i \times s_n – s_j \times s_n\} \\
\ \ =max\{g_j – s_j \times s_n\} – s_i^2 + s_i \times s_n $$
对于两个决策 $j,k\ (j \gt k)$
决策j比k优当且仅当 $g_j – g_k > (s_n-s_i) \times (s_j – s_k)$

$$\frac{g_j + g_k}{s_j – s_k} \gt s_n – s_i$$
故可以进行斜率优化
因为序列中的数有可能为0,所以需要注意斜率不存在的情况。
因为只有128M内存,需要滚动f数组

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
deque<int> s[210];
ll sum[N],f[2][N];
double calc(int j,int k,int p) {
	//j>k
	if(sum[j]==sum[k]) return -1e10;
	return (double)(f[p & 1][j]-f[p & 1][k])/(double)(sum[j]-sum[k]);
}
int a[N];
int main() {
	//freopen("3675.in","r",stdin);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=k;i++) {
		s[i].push_back(1);
		f[i&1][1]=sum[1]*(sum[n]-sum[1]);
	}
	s[0].push_back(0);
	for(int j=1;j<=k;j++) {
		 for(int i=2;i<=n;i++){          
			while(s[j-1].size()>1&&calc(s[j-1][s[j-1].size()-2],s[j-1].back(),j-1)>(sum[n]-sum[i]))  {
				s[j-1].pop_back();
			}
			f[j & 1][i]=f[(j-1) & 1][s[j-1].back()]+(sum[n]-sum[i])*(sum[i]-sum[s[j-1].back()]);
			while(s[j].size()>1&&calc(i,s[j].front(),j)>=calc(s[j].front(),s[j][1],j)) {
				s[j].pop_front();
			}
			s[j].push_front(i);
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++) {
		ans=max(ans,f[k & 1][i]);
	}
	printf("%lld\n",ans);
}

在UOJ上也有一道一样的题,需要输出方案,但空间给的256M
可以直接开一个数组记录答案
链接
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
deque<int> s[210];
ll sum[N],f[2][N];
int pre[210][N];
double calc(int j,int k,int p) {
	//j>k
	if(sum[j]==sum[k]) return -999999;
	return (double)(f[p & 1][j]-f[p & 1][k])/(double)(sum[j]-sum[k]);
}
int a[N];
int main() {
	freopen("3675.in","r",stdin);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	/*for(int i=1;i<=k;i++) {
		s[i].push_back(1);
		f[i&1][1]=sum[1]*(sum[n]-sum[1]);
	}*/
//	s[1].push_back(1);
	f[1&1][1]=sum[1]*(sum[n]-sum[1]);
	s[0].push_back(0);
//	f[1][1]=sum[1]*(sum[n]-sum[1]);
	for(int j=1;j<=k;j++) {
		 for(int i=j;i<n;i++){          
			while(s[j-1].size()>1&&calc(s[j-1][s[j-1].size()-2],s[j-1].back(),j-1)>(sum[n]-sum[i]))  {
				s[j-1].pop_back();
			}
			f[j & 1][i]=f[(j-1) & 1][s[j-1].back()]+(sum[n]-sum[i])*(sum[i]-sum[s[j-1].back()]);
			pre[j][i]=s[j-1].back();
			while(s[j].size()>1&&calc(i,s[j].front(),j)>=calc(s[j].front(),s[j][1],j)) {
				 
				s[j].pop_front();
			}
			s[j].push_front(i);
		}
	}
	ll ans=0;
	int pos=0;
	for(int i=1;i<n;i++) {
		if(f[k&1][i]>=ans) pos=i;
		ans=max(ans,f[k & 1][i]);
	}
	printf("%lld\n",ans);
	for(int i=k;i>=1;i--) {
		printf("%d ",pos);
		if(pre[i][pos]!=0) pos=pre[i][pos];
	}
//	printf("%d",pos);
}

Be the First to comment.

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注