「BZOJ3675」[Apio2014] 序列分割
Description
小H最近迷上了一个分割序列的游戏。在这个游戏里，小H需要将一个长
度为N的非负整数序列分割成k+l个非空的子序列。为了得到k+l个子序列，
小H将重复进行七次以下的步骤：
1．小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的
序列一一也就是一开始得到的整个序列）；
2．选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新
序列。
每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序
列中元素和的乘积。小H希望选择一种最佳的分割方案，使得k轮（次）之后，
小H的总得分最大。
Input
输入文件的第一行包含两个整数n和尼(k+1≤n)。
第二行包含n个非负整数a1，n2…．，an(0≤ai≤10^4)，表示一开始小H得
到的序列。
Output
一行包含一个整数，为小H可以得到的最大得分。
Sample Input
7 3
4 1 3 4 0 2 3
Sample Output
108
HINT
「样例说明」
在样例中，小H可以通过如下3轮操作得到108分：
1．-开始小H有一个序列(4，1，3，4，0，2，3)。小H选择在第1个数之后的位置
将序列分成两部分，并得到4×(1+3+4+0+2+3)=52分。
2．这一轮开始时小H有两个序列：(4)，(1，3，4，0，2，3)。小H选择在第3个数
字之后的位置将第二个序列分成两部分，并得到(1+3)×(4+0+2+
3)=36分。
3．这一轮开始时小H有三个序列：(4)，(1，3)，(4，0，2，3)。小H选择在第5个
数字之后的位置将第三个序列分成两部分，并得到(4+0)×(2+3)=
20分。
经过上述三轮操作，小H将会得到四个子序列：(4)，(1，3)，(4，0)，(2，3)并总共得到52+36+20=108分。
「数据规模与评分」
：数据满足2≤n≤100000,1≤k≤min(n -1，200)。
题解
感觉和顺序没什么关系。。。那么就很显然得出n^2k的dp方程
\(f_i=f_j+(s_i-s_j) \times s_j\)
接下来可以单调队列，也可以斜率优化啦。。。
\(s_i >(s_k^2 -s_j^2+f_j-f_k) \div (s_k-s_j)\)
分母分子会同时为0。。。干脆先扫一遍把0全去掉
斜率优化
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 9000000000000000000LL #define mp make_pair #define pa pair<ll,int> #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; ll sum[100005],f[100005],g[100005]; int a[100005],q[100005]; double cal(int j,int k) { return (double)(sum[k]*sum[k]-sum[j]*sum[j]+g[j]-g[k])/(double)(sum[k]-sum[j]); } void tran(int x) { int head=1,tail=0; for(int i=x;i<=n;i++) { while(head<tail&&cal(q[tail-1],q[tail])>cal(q[tail],i-1))tail--; q[++tail]=i-1; while(head<tail&&cal(q[head],q[head+1])<sum[i])head++; int t=q[head]; f[i]=g[t]+(sum[i]-sum[t])*sum[t]; } for(int i=x;i<=n;i++)swap(f[i],g[i]); } void dp() { for(int i=1;i<=K;i++) tran(i); printf("%lld\n",g[n]); } int main() { n=read();K=read(); for(int i=1;i<=n;i++)a[i]=read(); int top=0; for(int i=1;i<=n;i++)if(a[i]!=0)a[++top]=a[i]; n=top; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; dp(); return 0; } |
单调队列
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 9000000000000000000LL #define mp make_pair #define pa pair<ll,int> #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; ll a[100005],sum[100005],f[100005],g[100005]; struct data{ int l,r,p; }q[100005]; ll cal(int i,int j) { return g[i]+(sum[j]-sum[i])*sum[i]; } int find(data t,int q) { int l=t.l,r=t.r,mid; while(l<=r) { mid=(l+r)>>1; if(cal(q,mid)>cal(t.p,mid))r=mid-1; else l=mid+1; } return l; } void tran(int x) { int head=1,tail=0; q[++tail]=(data){0,n,x-1}; for(int i=x;i<=n;i++) { if(i>q[head].r)head++; f[i]=cal(q[head].p,i); if(tail<head||cal(i,n)>cal(q[tail].p,n)) { while(head<=tail&&cal(i,q[tail].l)>cal(q[tail].p,q[tail].l)) tail--; if(head<=tail) { int t=find(q[tail],i); q[tail].r=t-1; q[++tail]=(data){t,n,i}; } else q[++tail]=(data){i,n,i}; } } for(int i=x;i<=n;i++)swap(f[i],g[i]); } void dp() { for(int i=1;i<=K;i++) tran(i); printf("%lld\n",g[n]); } int main() { n=read();K=read(); for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i]; dp(); return 0; } |
OI 课件=>
确定两个都是单调队列不过第二个是维护凸包并在上面二分
没有看懂。。 为什么有两种。。不是合在一起用的吗？
斜率优化是省节点，单调队列省时间（虽然好像都差不多QWQ）
斜率优化O(n)，单调队列O(nlogn)。
单调队列O(n)谢谢
dalao你又D人了