首页 > 代码库 > [APIO2014]序列分割
[APIO2014]序列分割
斜率优化
f[i]=max(f[j]+s[j]*(s[i]-s[j]))
令g[i]=f[i]-s[i]^2
j比k优 那么g[j]+s[i]s[j]>g[k]+s[i][k]
g[j]-g[k]>s[i](s[k]-s[j])
g[j]-g[k]/(s[j]-s[k])<-s[i]
所以维护队列上凸即可
#include<iostream> #include<cstdio> #include<queue> #define MAXN 100000 #include<cstring> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,k; int from[202][MAXN+5]; ll f[MAXN+5]; ll s[MAXN+5]; ll g[2][MAXN+5]; int q[MAXN+5]; int top=0,tail=1; ll get(int pre,int x,int t) { while(top-tail>=1&&(g[pre][q[tail]]-g[pre][q[tail+1]])<s[x]*(s[q[tail+1]]-s[q[tail]])) ++tail; from[t][x]=q[tail]; return g[pre][q[tail]]+s[q[tail]]*s[x]; }; void ins(int t,int k) { while(top-tail>=1) { int i=q[top-1],j=q[top]; if((g[t][k]-g[t][j])*(s[i]-s[j])<(g[t][j]-g[t][i])*(s[j]-s[k])) top--; else break; } q[++top]=k; } int main() { //freopen("sequence.in","r",stdin); //freopen("sequence.out","w",stdout); n=read();k=read(); for(int i=1;i<=n;i++) { s[i]=read();s[i]+=s[i-1]; } int pre=0,nown=1; for(int i=1;i<=n;i++) g[pre][i]=-(s[i]*s[i]); for(int l=2;l<=k+1;l++) { memset(f,0,sizeof(f));top=0;tail=1; memset(g[nown],0,sizeof(g[nown])); ins(pre,l-1); for(int i=l;i<=n;i++) { f[i]=get(pre,i,l); g[nown][i]=f[i]-(s[i]*s[i]); if(s[i]!=s[i-1])ins(pre,i); //printf("%d %d %d %I64d\n",l,i,from[l][i],f[i]); } nown=1-nown; pre=1-pre; } printf("%lld\n",f[n]); return 0; }
[APIO2014]序列分割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。