洛谷 P3648 [APIO2014]序列分割 解题报告 P3648 [APIO2014]序列分割

题目描述

你正在玩一个关于长度为(n)的非负整数序列的游戏。这个游戏中你需要把序列分成(k+1)个非空的块。为了得到(k+1)块，你需要重复下面的操作(k)次：

选择一个有超过一个元素的块（初始时你只有一块，即整个序列）

选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

输入输出格式

输入格式：

第一行包含两个整数(n)和(k)。保证(k + 1 leq n)。

第二行包含(n)个非负整数(a_1, a_2, cdots, a_n(0 leq a_i leq 10^4))，表示前文所述的序列。

输出格式：

第一行输出你能获得的最大总得分。

第二行输出(k)个介于(1)到(n - 1)之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第(i)个整数(s_i)表示第(i)次操作将在(s_i)和(s_{i+1})之间把块分开。

如果有多种方案使得总得分最大，输出任意一种方案即可。

说明

第一个子任务共 11 分，满足 (1 leq k < n leq 10)。

第二个子任务共 11 分，满足 (1 leq k < n leq 50)。

第三个子任务共 11 分，满足 (1 leq k < n leq 200)。

第四个子任务共 17 分，满足 (2 leq n leq 1000, 1 leq k leq min{n - 1, 200})。

第五个子任务共 21 分，满足 (2 leq n leq 10000, 1 leq k leq min{n - 1, 200})。

第六个子任务共 29 分，满足 (2 leq n leq 100000, 1 leq k leq min{n - 1, 200})。

---

首先得玩出我们不需要做区间DP

因为切的顺序并不影响结果

然后令(dp[i][j])代表前(i)个切(j)次的最大得分

(dp[i][j]=max_{j le k < i}(dp[k][j-1]+f[k] imes (f[i]-f[k])))

开(k)个单调队列进行斜率优化（事实上一个就够了而我比较傻）

添加时其实很耐人寻味哦

---

Code:

#include <cstdio>
#define ll long long
ll min(ll x,ll y){return x<y?x:y;}
const int N=100010;
const int M=202;
ll dp[N][M],q[M][N],pre[N][M],l[M],r[M],f[N],n,k;
int ans[M],cnt=0;
ll Y(ll i,ll j)
{
    return dp[i][j-1]-f[i]*f[i];
}
ll X(ll i)
{
    return f[i];
}
ll K(ll i)
{
    return -f[i];
}
int main()
{
    //freopen("3675.in","r",stdin);
    //freopen("3675.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",f+i);
        f[i]+=f[i-1];
    }
    for(int i=1;i<=k;i++)
    {
        q[i][++r[i]]=1;
        ++l[i];
    }
    for(int i=2;i<=n;i++)
        for(int j=1;j<=min(i,k+1);j++)
        {
            while(l[j]<r[j]&&K(i)*(X(q[j][l[j]+1])-X(q[j][l[j]]))
               <=(Y(q[j][l[j]+1],j)-Y(q[j][l[j]],j))) l[j]++;
            dp[i][j]=dp[q[j][l[j]]][j-1]+f[q[j][l[j]]]*(f[i]-f[q[j][l[j]]]);
            pre[i][j]=q[j][l[j]];
            while(l[j]<r[j]&&(Y(i,j)-Y(q[j][r[j]],j))*(X(q[j][r[j]])-X(q[j][r[j]-1]))
               >=(X(i)-X(q[j][r[j]]))*(Y(q[j][r[j]],j)-Y(q[j][r[j]-1],j))) r[j]--;
            q[j][++r[j]]=i;
        }
    printf("%lld
",dp[n][k]);
    int pos=n,cut=k;
    while(cut)
    {
        pos=pre[pos][cut--];
        ans[++cnt]=pos;
    }
    for(int i=cnt;i;i--)
        printf("%d ",ans[i]);
    return 0;
}

---

2018.7.25