0%

Project3648_[APIO2014]序列分割项目报告

摘要:斜率优化

P3648 [APIO2014]序列分割

题面

题目分析

降智的是,得到的答案和切序列的顺序无关,最后得到的项是一样的.

还是考虑dp,设$f_{i,j}$表示前i个数分j次得到的最大分数.

那么有(s为前缀和):

$f_{i,j} = max\{ f_{l,j} + s_{l}(s_i-s_l)\} (1 \leq l < i)$

可以优化为滚动数组,推导时用$f_i$表示$f_{i,j-1}$.

仿造上一篇博客里面使用的思考方式,我们在转移到i时,k比j优秀,于是有:

$f_k + s_ks_i - s_k^2 > f_j + s_js_i - s_j^2$

考虑将$s_i$作为斜率,整理得:

$\frac{f_k-s_k^2-(f_j-s_j^2)}{-s_k-(-s_i)} > s_i$

$s_i$单调递增,$-s_i$作为x单调递增,维护一个下凸壳.

然后这题代码巨恶心…

代码

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
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "cstdlib"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=100010,maxk=210;
lxl n,k,l,r;
lxl s[maxn],f[maxn],cur[maxn],from[maxk][maxn],q[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline double slope(lxl i,lxl j)
{
lxl xa=-s[i],xb=-s[j];
lxl ya=cur[i]-(s[i]*s[i]),yb=cur[j]-(s[j]*s[j]);
if(xa==xb)return -INF;
else return (double)(ya-yb)/(double)(xa-xb);
}
int main(void)
{
n=read(),k=read();
for(R int i(1);i<=n;++i)s[i]=read()+s[i-1];
for(R int bo(1);bo<=k;++bo)
{
l=r=0;
for(R int i(1);i<=n;++i)cur[i]=f[i],f[i]=0;
for(R int i(1);i<=n;++i)
{
while(l+2<=r&&slope(q[l],q[l+1])<=s[i])++l;
if(l<r)
{
from[bo][i]=q[l];
f[i]=cur[q[l]]+s[q[l]]*(s[i]-s[q[l]]);
}
while(l+2<=r&&slope(q[r-2],q[r-1])>=slope(q[r-1],i))--r;
q[r++]=i;
}
}
printf("%lld\n",f[n]);
for(R int i(from[k][n]);k;i=from[--k][i])printf("%d ",i);
printf("\n");
return 0;
}