YZOJ P2021 [APIO2014]sequence
时间限制：2000MS 内存限制：131072KB
难度： \(5.7\)
-
题目描述
给定一个长度为 \(N\) 的非负整数序列 \(a\) ，现要把它分割成 \(k+1\) 个连续非空的子序列。
每次分割可以选择一段剩余长度超过 \(1\) 的序列，并在其中选择一个位置，把它分割成两个连续非空的子序列。这样做可以得到一些 \(Bonus\)，为分割出的两个新序列中元素和的乘积。
现要找到一种方案，使得经过 \(k\) 次分割后，能得到的 \(Bonus\) 最多。
-
输入格式
第一行包含两个整数 \(n, k\) ；
第二行包含 \(n\) 个非负整数，表示序列 \(a\) 。
-
输出格式
第一行包含一个整数，为最大 \(Bonus\) 。
第二行包含 \(k\) 个 \(1\) 到 \(n-1\) 的整数，表示最优方案。其中第 \(i\) 个数 \(x_i\) 表示在该方案中，进行第 \(i\) 次操作时，应该选择第 \(x_i\) 个数后面的位置，并将这个数所在的序列分成两部分。
如果有多个最优方案，输出其中任意一种即可。
-
样例输入
|
1 2 |
7 3 4 1 3 4 0 2 3 |
-
样例输出
|
1 2 |
108 1 3 5 |
-
数据规模与约定
数据满足 \(2 \leq n \leq 100000\)，\(1 \leq k \leq min\{n-1,200\}\) 。
套路题，设 \(f_{i, k}\) 为割到第 \(i\) 个数且已经割了 \(k\) 刀时 \(Bonus\) 的最大值，计 \(sum\) 为 \(a\) 的前缀和。
所以 \(f_{i, k}=\min\limits_{j=1}^{i-1}\{f_{j, k-1}+sum_j(sum_i-sum_j)\}\) 。
这样就是 \(O(kN^2)\) 无法通过本题。
不难发现其实这是一个斜率优化的经典模型。对这个转移方程进行一些处理
\(\begin{align} f_{i, k} &=f_{j, k-1}+sum_j(sum_i-sum_j) \\ \underbrace{f_{i, k}}_{b_i} &=\underbrace{f_{j, k-1}-sum^2_j}_{y_j}+\underbrace{sum_i}_{k_i} \cdot \underbrace{sum_j}_{-x_j} \end{align}\)
这里的 \(k_i\) 和 \(x_j\) 都是单调的，直接上单调队列 \(O(kN)\) 即可。
值得注意的是，\(x_j\) 是递减的，所以判断的时候符号要反过来。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif typedef long long LLONG; inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return a; } int sum[105050]; LLONG f[105050][2]; int path[105050][205],stk[205]; struct _point { LLONG x,y;int wh; LLONG operator * (const _point&o)const { return (x*o.y-y*o.x); } _point operator - (const _point&o)const { return (_point){x-o.x,y-o.y}; } }list[105050]; int front,rear; int main() { register int N=getnum(),K=getnum(),oK=K; for(register int i=1;i<=N;i++) sum[i]=sum[i-1]+getnum(); /*for(register int k=1;k<=K;k++) for(register int i=k;i<=N;i++) for(register int j=1;j<i;j++) { ULLONG tf=f[j][k-1]+sum[j]*(sum[i]-sum[j]); if(tf>f[i][k]) f[i][k]=tf,path[i][k]=j; }*/ for(register int k=1,x=0;k<=K;k++,x^=1) { front=rear=0; for(register int i=k;i<=N;i++) { _point ts=(_point){1,sum[i],0}; while(front+1<rear && (list[front+1]-list[front])*ts<=0) front++; if(front<rear) f[i][x]=list[front].y-(LLONG)list[front].x*sum[i],path[i][k]=list[front].wh; _point tn=(_point){-sum[i],f[i][x^1]-(LLONG)sum[i]*sum[i],i}; while(front+1<rear && (list[rear-1]-list[rear-2])*(tn-list[rear-1])<=0) rear--; list[rear++]=tn; } } printf("%lld\n",f[N][(K+1)&1]); while(K) N=path[N][K],stk[K]=N,K--; for(register int i=oK;i>=1;i--) printf("%d ",stk[i]); printf("\n"); return 0; } |