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 1000000000 24 25 #define maxn 100000+1000 26 27 #define maxm 201 28 29 #define eps 1e-10 30 31 #define ll long long 32 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 1000000007 44 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 }
为何贼慢？难道应为实数的问题？