首页 > 代码库 > UOJ104 【APIO2014】Split the sequence

UOJ104 【APIO2014】Split the sequence

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

 

 

 

本文作者:ljh2000 
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

 

题目链接:http://uoj.ac/problem/104

正解:DP+斜率优化

解题报告:

  容易发现,答案只和分割处有关,与顺序无关。

  所以朴素方程很容易得到:

  令${S[n]=\sum_{i=1}^{n}a[i]}$

  ${f[i][k]=max(f[j][k-1]+S[j]*(S[i]-S[j])) ,j<i}$  

  对于${j1,j2}$且满足${j1<j2}$,${f[j1][k-1]<f[j2][k-1]}$,显然$j1$可以被删除,则

  ${f[j1][k-1]+S[j1]*(S[i]-S[j1]) < f[j2][k-1]+S[j2]*(S[i]-S[j2])}$   

  化简后:

  ${f[j1][k-1]-f[j2][k-1]+S[j2]^2-S[j1]^2 > S[i]*(S[j2]-S[j1])}$

  令${g[i][k]=f[i][k]-S[i]^2}$

  则${g[j1][k-1]-g[j2][k-1]>S[i]*(S[j2]-S[j1])}$

  到了这一步,正解就已经呼之欲出了。显然我们可以用斜率优化+单调队列,把DP优化到$O(nk)$,做k次,每次只需扫一遍。

  队首如果满足上式,则直接删掉。加入队尾的时候,看一下斜率的变化趋势,如果不满足则pop掉。

  

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <complex>
using namespace std;
typedef long long LL;
const int MAXN = 100011;
int n,k,dui[MAXN],head,tail;
LL g[MAXN],s[MAXN],f[MAXN],F[MAXN];
int ans[MAXN],pre[MAXN][211];
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline LL calc(int i,int j1,int j2){ return s[i]*(s[j2]-s[j1]); }

inline void work(){
	n=getint(); k=getint(); for(int i=1;i<=n;i++) s[i]=getint();
	for(int i=2;i<=n;i++) s[i]+=s[i-1]; for(int i=1;i<=n;i++) g[i]=-s[i]*s[i];
	for(int nowk=2;nowk<=k+1;nowk++) {
		head=tail=0;
		dui[++tail]=nowk-1;
 		for(int i=nowk;i<=n;i++) {
			while(head<tail && calc(i,dui[head],dui[head+1])>=(g[dui[head]]-g[dui[head+1]])) head++;
			F[i]=f[dui[head]]+s[dui[head]]*(s[i]-s[dui[head]]); pre[i][nowk-1]=dui[head];
			while(head<tail && (g[dui[tail-1]]-g[dui[tail]])*(s[i]-s[dui[tail]]) >= (g[dui[tail]]-g[i])*(s[dui[tail]]-s[dui[tail-1]])) 
				tail--;
			dui[++tail]=i;
		}
		for(int i=nowk;i<=n;i++) f[i]=F[i],g[i]=F[i]-s[i]*s[i];
	}
	printf("%lld\n",F[n]);
	for(int i=n,j=k;i>0;j--) i=pre[i][j],ans[j]=i;
	for(int i=1;i<=k;i++) printf("%d ",ans[i]);
}

int main()
{
    work();
    return 0;
}

  

  

UOJ104 【APIO2014】Split the sequence