首页 > 代码库 > BZOJ3675: [Apio2014]序列分割
BZOJ3675: [Apio2014]序列分割
3675: [Apio2014]序列分割
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 218 Solved: 82
[Submit][Status]
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
4 1 3 4 0 2 3
Sample Output
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)。
Source
题解：
这题比较巧妙的转化是：最后得分只与最后分成了哪几个序列有关，而与分的先后顺序无关。（想了好久才想出来T_T)
然后我们就可以DP了，f[i]=min(f[j]+(s[i]-s[j])*(n-s[i]+s[j])) 稍作变形可知这可以用斜率来优化，所以此题就解了。
具体变形可以移步 http://trinklee.blog.163.com/blog/static/238158060201462310236608/
因为写斜率 没有特判分母==0 WA了2次。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 100000+100026 27 #define maxm 20128 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline int read()48 49 {50 51 int x=0,f=1;char ch=getchar();52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57 return x*f;58 59 }60 int n,m,t=0,q[maxn];61 ll f[2][maxn],s[maxn];62 inline double k(int i,int j)63 {64 if(s[i]-s[j]<eps)return inf;65 else return (double)(f[1-t][i]-s[i]*s[i]-f[1-t][j]+s[j]*s[j])/(double)(s[i]-s[j]);66 }67 68 int main()69 70 {71 freopen("input.txt","r",stdin);72 freopen("output.txt","w",stdout);73 n=read();m=read();74 s[0]=0;75 for1(i,n)s[i]=s[i-1]+read();76 for1(i,n)f[0][i]=s[i]*(s[n]-s[i]);77 for1(j,m)78 {79 t=1-t;80 int l=1,r=0;81 for1(i,n)82 {83 while(l<r&&k(q[l+1],q[l])>s[n]-2*s[i])l++;84 f[t][i]=f[1-t][q[l]]+(s[i]-s[q[l]])*(s[n]-s[i]+s[q[l]]);85 if(i<j+1)f[t][i]=0;86 if(i==j+1)f[t][i]=f[1-t][i-1]+(s[i]-s[i-1])*(s[n]-s[i]+s[i-1]);87 while(l<r&&k(i,q[r])>k(q[r],q[r-1]))r--;88 q[++r]=i;89 }90 }91 printf("%lld\n",f[t][n]>>1);92 93 return 0;94 95 }
为何贼慢？难道应为实数的问题？
BZOJ3675: [Apio2014]序列分割