UOJ#104. 【APIO2014】Split the sequence 动态规划 斜率优化

时间：2021-06-03 15:02:15

原文链接www.cnblogs.com/zhouzhendong/p/UOJ104.html

题解

首先证明一个结论：对于一种分割方案，分割的顺序不影响最终结果。

证明：对于树 a[x] 和 a[y] ，如果 x 与 y 之间有分割，那么它们对答案的贡献就是 a[x] * a[y] ，否则无贡献。

于是问题转化成 DP： 设 dp[i][j] 表示把前 j 个数分成 i 段的最大收益，那么：

设

$$s[k] = \sum_{i=1}^{k} a[i]$$

$$dp[i][j] = \max_{0\leq k<j}(dp[i-1][k] + (s[j] - s[k])s[k])$$

直接斜率优化即可。

代码

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof (x))

#define For(i,a,b) for (int i=a;i<=b;i++)

#define Fod(i,b,a) for (int i=b;i>=a;i--)

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

#define fi first

#define se second

#define real __zzd001

#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

#define outval(x) printf(#x" = %d\n",x)

#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")

#define outtag(x) puts("----------"#x"----------")

#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\

						For(_v2,L,R)printf("%d ",a[_v2]);puts("");

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef vector <int> vi;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=100005,K=205;

const LL INF=1e18;

int n,k;

int a[N],s[N];

LL dp[K][N];

int pre[K][N];

LL x[N],y[N];

int q[N],head,tail;

double pos(int a,int b){

	return (double)(x[a]-x[b])/(y[b]-y[a]);

}

void Push(int i,int j){

	if (dp[i][j]>=0){

		x[j]=dp[i][j]-(LL)s[j]*s[j];

		y[j]=s[j];

		while (head<=tail&&y[j]==y[q[tail]]){

			if (x[j]<=x[q[tail]])

				return;

			tail--;

		}

		while (head<tail&&pos(q[tail],j)<=pos(q[tail-1],q[tail]))

			tail--;

		q[++tail]=j;

	}

}

int main(){

	n=read(),k=read()+1;

	For(i,1,n)

		a[i]=read(),s[i]=s[i-1]+a[i];

	For(i,0,K-1)

		For(j,0,N-1)

			dp[i][j]=-INF;

	dp[0][0]=0;

	For(i,1,k){

		head=1,tail=0;

		clr(x),clr(y);

		Push(i-1,0);

		For(j,1,n){

			while (head<tail&&pos(q[head],q[head+1])<=s[j])

				head++;

			if (head<=tail){

				dp[i][j]=x[q[head]]+y[q[head]]*s[j];

				pre[i][j]=q[head];

			}

			Push(i-1,j);

		}

	}

	cout<<dp[k][n]<<endl;

	int x=pre[k][n];

	while (--k)

		printf("%d ",x),x=pre[k][x];

	return 0;

}

/*

dp[i][j] = max_{0<=k<j}(dp[i-1][k] + (s[j] - s[k]) * s[k])

dp[i][j] = max_{0<=k<j}(dp[i-1][k] - s[k] * s[k] + s[j] * s[k])

*/

　　

相关文章