首页 > 代码库 > BZOJ 3675 APIO2014 序列分割 斜率优化
BZOJ 3675 APIO2014 序列分割 斜率优化
题目大意:给定一个序列,可以分割k次,每次分割的得分为两段序列的和的乘积 求最大得分
首先我们可以推出序列的分割顺序是不影响得分的 比如说我要把一个序列分割成四份ABCD 我先分割A BCD或者先分割AB CD最后的得分是一样的
证明?嗯……易证。显然嘛。哈哈。好吧我不会证。。。自己画一下推推就好
好吧这是神犇的证法:比如我将ABCD分割为AB CD 那么A就和CD各乘了一次 B也和CD各乘了一次 再分割AB时A和B也乘了一次 最后可以保证所有的序列对(X,Y)在任何一种分割法中都只乘了一次
然后就很显然了 我们令f[i][k]为将前i个元素分成k块的最大分数,那么就有
f[i][k]=max{ f[j][k-1] + sum[j]*(sum[i]-sum[j]) }
令P=f[j][k-1]-sum[j]*sum[j]+sum[i]*sum[j]
则有sum[j]*sum[j]-f[j][k-1]=sum[i]*sum[j]-P
其中X[j]=sum[j],Y[j]=sum[j]*sum[j]-f[j][k-1],s[i]=sum[i],查询斜率单调,可以套用单调队列,维护下凸包即可
注意x可能相等 计算斜率时要特判
我这个沙茶一开始居然认为f[i][1]=sum[i]...桑不起啊
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 100100 using namespace std; typedef long long ll; struct point{ ll x,y; double slope; point(){} point(ll _,ll __):x(_),y(__),slope(0.0){} }q[M]; int n,k,r,h; int a[M]; ll sum[M],f[M][2]; inline double Get_Slope(const point &x,const point &y) { if(x.x==y.x) return 2147483647*(y.y>x.y?1:-1); return (double)(y.y-x.y)/(y.x-x.x); } void Insert(point p) { double s=0; while(r!=h) { s=Get_Slope(q[r],p); if(r==h+1) break; if(s<q[r].slope) r--; else break; } q[++r]=p; q[r].slope=s; } point Get_Ans(double s) { while(r!=h+1&&q[h+2].slope<s) ++h; return q[h+1]; } int main() { int i,j; cin>>n>>k; for(i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; for(j=2;j<=k+1;j++) { r=h=0; for(i=j;i<=n;i++) { Insert( point(sum[i-1],sum[i-1]*sum[i-1]-f[i-1][~j&1]) ); point p=Get_Ans(sum[i]); f[i][j&1]=sum[i]*p.x-p.y; } } cout<<f[n][~k&1]<<endl; }
BZOJ 3675 APIO2014 序列分割 斜率优化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。