[bzoj 3675][Apio2014] 序列分割

Contents

1 Description
2 Input
3 Output
4 Sample Input
5 Sample Output
6 HINT
7 Solution

Description

小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：

1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；

2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。

每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。

Input

输入第一行包含两个整数n，k（k+1≤n）。

第二行包含n个非负整数a1，a2，...，an（0≤ai≤10^4），表示一开始小H得到的序列。

Output

输出第一行包含一个整数，为小H可以得到的最大分数。

Sample Input

7 3
4 1 3 4 0 2 3

Sample Output

108

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)。

Solution

总算斜率有点上手了

设 $f(i,j)$ 表示前 $i$ 块切了 $j$ 次的最大积分

有

$f[i][j]=max\begin{Bmatrix}f[k][j-1]+s[k]\times (s[i]-s[k])\end{Bmatrix}$

时间复杂度 $O(n^{2}k)$ ，显然会 $TLE$

发现 $s$ 单调增，容易推导出 $f$ 单调增，然后斜率优化xjb搞搞就行了

因为要保证整体是向上的，所以要维护一个上凸壳

单调队列瞎搞搞就好了

#include <iostream>
#include <cstdio>
using namespace std;
 
const int N = 100050;
typedef long long LL;
 
int q[N],front,tail;
int n,m;
LL f[N][2],sum[N];
 
void readInt(int &x)
{
    x = 0; char c = '.';
    while(c < '0' || c > '9') c = getchar();
    while(c >='0' && c <='9') x = x * 10 + c - '0', c = getchar();
}
 
void readLong(LL &x)
{
    x = 0; char c = '.';
    while(c < '0' || c > '9') c = getchar();
    while(c >='0' && c <='9') x = x * 10 + c - '0', c = getchar();
} 
 
void getDP(int i,int j,int s)
{
    f[i][s] = f[j][s^1] + sum[j] * (sum[i] - sum[j]);
}
 
LL Y(int j,int k,int s)
{
    return f[j][s] - sum[j] * sum[j] - f[k][s] + sum[k] * sum[k];
}
 
LL X(int j,int k)
{
    return sum[k] - sum[j];
}
 
int main()
{
    int i,j,s,now,las;
    readInt(n); readInt(m);
    for(i = 1; i <= n; ++ i)
    {
        readLong(sum[i]);
        sum[i] += sum[i-1];
    }
    for(s = 1; s <= m; ++ s)
    {
        front = tail = 0; q[front] = 0;
        for(now = s & 1, las = now ^ 1, i = 1; i <= n; ++ i)
        {
            while(front < tail && Y(q[front],q[front+1],las) <= sum[i] * X(q[front],q[front+1]))
                ++ front;
            getDP(i,q[front],now);
            while(front < tail && Y(i,q[tail],las) * X(q[tail],q[tail-1]) <= Y(q[tail],q[tail-1],las) * X(i,q[tail]))
                -- tail;
            q[++tail] = i;
        }
    }
    printf("%lld\n",f[n][m&1]);
    return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

const int N = 100050;

typedef long long LL;

int q[N],front,tail;

int n,m;

LL f[N][2],sum[N];

void readInt(int &x)

{

x = 0; char c = '.';

while(c < '0' || c > '9') c = getchar();

while(c >='0' && c <='9') x = x * 10 + c - '0', c = getchar();

}

void readLong(LL &x)

{

x = 0; char c = '.';

while(c < '0' || c > '9') c = getchar();

while(c >='0' && c <='9') x = x * 10 + c - '0', c = getchar();

}

void getDP(int i,int j,int s)

{

f[i][s] = f[j][s^1] + sum[j] * (sum[i] - sum[j]);

}

LL Y(int j,int k,int s)

{

return f[j][s] - sum[j] * sum[j] - f[k][s] + sum[k] * sum[k];

}

LL X(int j,int k)

{

return sum[k] - sum[j];

}

int main()

{

int i,j,s,now,las;

readInt(n); readInt(m);

for(i = 1; i <= n; ++ i)

{

readLong(sum[i]);

sum[i] += sum[i-1];

}

for(s = 1; s <= m; ++ s)

{

front = tail = 0; q[front] = 0;

for(now = s & 1, las = now ^ 1, i = 1; i <= n; ++ i)

{

while(front < tail && Y(q[front],q[front+1],las) <= sum[i] * X(q[front],q[front+1]))

++ front;

getDP(i,q[front],now);

while(front < tail && Y(i,q[tail],las) * X(q[tail],q[tail-1]) <= Y(q[tail],q[tail-1],las) * X(i,q[tail]))

-- tail;

q[++tail] = i;

}

printf("%lld\n",f[n][m&1]);

return 0;

}

mps' blog

[bzoj 3675][Apio2014] 序列分割

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

发表评论取消回复

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

发表评论 取消回复

发表评论取消回复