洛谷 3648 bzoj 3675 [APIO2014]序列分割 题解

发表于 | 更新于 | 阅读次数：
本文字数： 34 字 | 阅读时长 ≈ 1 分钟

题意简述

给定一个长度为的序列，和一个。将切次，划分成个段，每切一次产生分数就是姓切出来的两个段的和的乘积。请你最大化分数（还要记录在哪里切的）。

思路

。在之间。

(矢量图，随便放大)斜率优化一下顺便记录答案即珂。

具体思路

先证明分数和切的顺序没有关系。

设原序列珂以分为三个段，和为。

  1. 先切，再切：
  2. 先切，再切：

所以是一样的。显然这个结论有珂扩展性，即如果原序列划分成更多的块，也能三个三个的合并，并得到同样的结果。证毕。

设表示前个数切刀的最大分数，然后枚举上一次分开的位置，用前缀和维护一下就能得到上面那个方程了。但是很显然这个是的，过不去。

考虑斜率优化。由于只和有关，所以设表示，表示。然后：

考虑两个转移点。如果比优，那么：

把每个点看作是，然后我们发现，由于是单调递增的，所以这个的斜率也是单调递增的（不明白去找斜率优化的笔记看看。。。）

然后对于队首的元素，如果斜率低于了，也就出队了。维护一下即珂。

实现注意

  1. 记录答案：设表示时选择的最优的。然后不断往前跳即珂输出答案。
  2. 空间开不下，记得用滚动数组维护（或者只需要一个和一个即珂）
  3. 勿忘

代码：

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
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define int long long 
    #define real double
    #define EPS 1e-7
    #define N 155555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int n,k,a[N];
    int s[N];
    void Input()
    {
        R1(n),R1(k);
        F(i,1,n) 
        {
            R1(a[i]);
            s[i]=s[i-1]+a[i];
        }
    }

    int f[N],g[N];
    int pre[N][201];
    int x(int i){return g[i]-s[i]*s[i];}
    int y(int i){return -s[i];}
    //抽象成点
    double slope(int a,int b)
    {
        real dx=x(a)-x(b);
        real dy=y(a)-y(b);
        return (fabs(dy)<EPS)?-1e18:(dx/dy);
    }//计算斜率
    int Q[N],head,tail;
    void Soviet()
    {
        head=1,tail=1;
        Q[tail]=0;
        F(p,1,k)
        {
            FK(Q);
            FK(f);
            head=tail=1;
            Q[tail]=0;
            
            F(i,1,n)
            {
                while(head<tail and slope(Q[head],Q[head+1])<=s[i]) ++head;//斜率<=s[i]的出去
                int j=Q[head];
                f[i]=g[j]+s[j]*(s[i]-s[j]);
                pre[i][p]=j;//记录从哪里转移的
                while(head<tail and slope(Q[tail-1],Q[tail])>=slope(Q[tail],i)) --tail;
                Q[++tail]=i;//加入队列
            }
            F(i,1,n) g[i]=f[i];//别忘了滚动
        }

        printf("%lld\n",f[n]);
        int cur=n;
        D(i,k,1) cur=pre[cur][i],printf("%lld%c",cur," \n"[i==1]);
    }
    void IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}

w