「APIO2014」序列分割 - 斜率优化 | Bill Yang's Blog

「APIO2014」序列分割 - 斜率优化

题目大意

    小H最近迷上了一个分割序列的游戏。在这个游戏里,小H需要将一个长度为$N$的非负整数序列分割成$k+1$个非空的子序列。为了得到$k+1$个子序列,小H将重复进行$k$次以下的步骤:
1.小H首先选择一个长度超过$1$的序列(一开始小H只有一个长度为$n$的序列一一也就是一开始得到的整个序列);
2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序 列中元素和的乘积。小H希望选择一种最佳的分割方案,使得$k$轮(次)之后,小H的总得分最大。


题目分析

此题较垃圾,卡空间卡常数(需要用FastIO且不能用除法,除法太慢)

$\because a(b+c)+bc=(a+b)c+ab$
$\therefore$分割的顺序对结果不造成影响,可以进行Dp

$f[i,j]$表示前$i$个数,分裂成了$j$个区间的最大总得分。

方程拆开后发现可以斜率优化,推一下式子发现斜率优化维护上凸包即可。
注意不能算斜率,因为分母可以为$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<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T) {T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
LL Get_Int() {
LL res=0,bj=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)) {res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;

const int maxn=100005,maxk=2;

int n,m,Q[maxn];
LL sum[maxn],f[maxn][maxk];

double Up(int i,int j,int con) {
return (double)(f[j][con]-sum[j]*sum[n]-(f[i][con]-sum[i]*sum[n]));
}

LL Down(int i,int j) {
return (sum[j]-sum[i]);
}

int main() {
n=Get_Int();
m=Get_Int()+1;
for(int i=1; i<=n; i++)sum[i]=sum[i-1]+Get_Int();
for(int j=1; j<=m; j++) {
int Left=1,Right=1;
Q[1]=0;
f[0][j&1]=0;
for(int i=1; i<=n; i++) {
while(Left<Right&&Up(Q[Left],Q[Left+1],(j-1)&1)>=-sum[i]*Down(Q[Left],Q[Left+1]))Left++;
int Front=Q[Left];
f[i][j&1]=f[Front][(j-1)&1]+(sum[i]-sum[Front])*(sum[n]-sum[i]);
while(Left<Right&&Up(Q[Right-1],Q[Right],(j-1)&1)*Down(Q[Right],i)<=Up(Q[Right],i,(j-1)&1)*Down(Q[Right-1],Q[Right]))Right--;
Q[++Right]=i;
}
}
printf("%lld\n",f[n][m&1]);
return 0;
}
姥爷们赏瓶冰阔落吧~
0%