BZOJ 3675 [Apio2014]序列分割 (斜率优化DP)

洛谷传送门

题目大意：让你把序列切割k次，每次切割你能获得这一整块两侧数字和的乘积的分数，求最大的分数并输出切割方案

神题= =

搞了半天也没有想到切割顺序竟然和答案无关...我太弱了

证明很简单，就是乘法分配律，把式子展开就行了

定义$s_{i}$为序列$a$的前缀和，定义$f[k][i]$表示第$k$次切割是在第$i$个位置的后面，$f[k][i]=max(f[k-1][j]+(s_{i}-s_{j})*(s_{n}-s_{i}))$

展开式子，移项，发现$x$递增，斜率$k$也递增，用队列维护上凸包就行了

至于记录方案，另开一个数组，记录从哪转移来的就行了

复杂度$O(nk)$

又没长记性把$i$打成$j$了（捂脸）

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 101000

 #define M1 205

 #define ll long long

 #define dd double

 #define uint unsigned int

 #define idx(X) (X-'0')

 using namespace std;

 int gint()

 {

     ll ret=;int fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,K;

 int a[N1];

 ll sa[N1],f[][N1],x[N1],y[N1];

 int fa[M1][N1];

 int que[N1],ret[N1];

 int main()

 {

     freopen("t2.in","r",stdin);

     scanf("%d%d",&n,&K);

     for(int i=;i<=n;i++)

         a[i]=gint(),sa[i]=sa[i-]+a[i];

     int now=,pst=;

     for(int k=;k<=K;k++)

     {

         int hd=,tl=,j;

         que[++tl]=;

         for(int i=;i<n;i++)

         {

             while(hd+<=tl&&(y[que[hd+]]-y[que[hd]])>=-(x[que[hd+]]-x[que[hd]])*sa[i])

                 hd++;

             j=que[hd];

             f[now][i]=f[pst][j]+(sa[i]-sa[j])*(sa[n]-sa[i]);

             fa[k][i]=j;

             x[i]=sa[i],y[i]=f[pst][i]-sa[i]*sa[n];

             while(hd+<=tl&&(y[i]-y[que[tl-]])*(x[que[tl]]-x[que[tl-]])>=(y[que[tl]]-y[que[tl-]])*(x[i]-x[que[tl-]]))

                 tl--;

             que[++tl]=i;

         }swap(now,pst);

     }

     ll ans=,id=;

     for(int i=;i<n;i++)

         if(f[pst][i]>ans)

         ans=f[pst][i],id=i;

     for(int k=K;k>=;k--)

         ret[k]=id,id=fa[k][id];

     printf("%lld\n",ans);

     for(int k=;k<=K;k++)

         printf("%d ",ret[k]);

     puts("");

     return ;

 }

巴特西

BZOJ 3675 [Apio2014]序列分割 (斜率优化DP)

最新文章

热门文章