题解：[Apio2014]序列分割

其实下面的这个题是一个简化版本，原题要给dp数组开滚动数组，这个很简单就不写了；还有就是原题要输出方案，注释在代码里。

Luogu: [APIO2014] 序列分割

---

题面

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例

样例输入

7 3 
4 1 3 4 0 2 3 

样例输出

108 

数据范围与提示

数据满足2≤n≤100000,1≤k≤min(n -1，200)。

注意，输入的a[i]里可能有0

---

解法

转移方程

$f[l][r][k]$: 将[l,r]这个区间，切k刀，所能得到的最大得分

$f[l][r][k]:\underset{i=1\dots n-1,j=0..k-1}{max}f[l][i][j]+f[i+1][r][k-1-j]+(sum[r]-sum[i])\ast (sum[i]-sum[l-1])$

p.s. 当我们确定了最后切分出来的是哪些区间，我们的答案就是一样的

时间复杂度 $O(n^4)$

使用前缀和优化：

$f[m][i]$: 前 $a[1]..a[i]$ 分成m段，这前m段所贡献的最大得分和

记 $s[i]=\sum _{k=1..i}a[k]$

$f[m][i]=\underset{j=0..i-1}{max}f[m-1][j]+(s[i]-s[j])\ast s[j]$

优化

法1：分离变量后使用单调队列

$s[i]$: 前缀和

$f[m][i]=\underset{j=0..i-1}{max}f[m-1][j]+(s[i]-s[j])\ast s[j]$

从小到大枚举m，固定当前m，考虑到当前在计算f[m][i]:

假如有两个不同决策点j,k，尝试分析它们谁更优:

不妨设 j<k<i

对于当前的i，k比j更优等价于:

将j,k分到不等式一侧，i分到另一侧得：

$s[i]>(f[m-1][j]-f[m-1][k]-s[j{]}^2+s[k{]}^2)/(s[k]-s[j])$

记右式为 $g(j,k)$，左式为 $h(i)$

对于固定的m，有jg(j,k)$

三个决策点，易知，有 j1g(j2,h3)$ ，j2不会成为最优决策点，所以可以直接舍去

双端队列维护j[l]…j[r]从小到大，g函数也是从小到大的

对于任意 $l+1<=x<=r-1$ 有：$g(j[x-1],j[x])<g(j[x],j[x+1])$

//框架
for m=1..k
	queue q, l=r=1, q[1]=0
	for i=1..n
		while l+1<=r and h(i)>g(j[l],j[l+1])
			l++
		j[l]为决策点，更新dp[m][i]
		while l+1<=r and g(j[r-1],j[r])>g(j[r],i)
			r--
		j[++r]=i

然后我们可以解决本题

#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

int n,k;
int a[100005];
ll s[100005];

int q[100005];
ll dp[100005][205];
//int pre[100005][205];

double g(int x,int y,int z)
{
	if(s[x]==s[y])
	{
		return -1e18;
	}
    return (double)(s[x]*s[x]-s[y]*s[y]-dp[x][z-1]+dp[y][z-1])/(s[x]-s[y]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	
	for(int j=1;j<=k;j++)
	{
		int l=1,r=1;
		q[1]=0;
		for(int i=1;i<=n;i++)
		{
			while(l<r&&g(q[l],q[l+1],j)<=s[i])
			{
				l++;
			}
            
//			pre[i][j]=q[l];
			dp[i][j]=dp[q[l]][j-1]+s[q[l]]*(s[i]-s[q[l]]);
			
			while(l<r&&g(q[r-1],q[r],j)>=g(q[r],i,j))
			{
				r--;
			}
			q[++r]=i;
		}
		
	}
	
	cout<<dp[n][k]<<"\n";
//	for(int x=n,i=k;i>=1;i--)
//	{
//		x=pre[x][i];
//		cout<<x<<" ";
//	}
    
	return 0;
}

法2：斜率优化（aka 数形结合）

$f[m][i]=\underset{j=0..i-1}{max}f[m-1][j]+(s[i]-s[j])\ast s[j]$

=$f[m-1][j]-s[j]s[j]+s[j]s[i]$

$A(j)=f[m-1][j]-s[j]\ast s[j]$

$B(j)=s[j]$

$C(i)=s[i]$

相当于我们有若干个选项 j，每个j提供一个一次函数 y[j]

$y[j]=A(j)+B(j)\ast x$

对于所有 $y[0]..y[i-1]$，找一个最大的作为 $f[m][i]$ 的答案

此时我们维护若干个一次函数，要支持插入和求最大值

对于本题的特殊的单调性，即每次插入的 $B(j)$, $C(i)$ （斜率和横坐标）都是递增的

于是，我们可以用双端队列来维护

//框架
struct line
{
	int a,b;
} q[];

for m=1..k
	q.clear(),l=r=1,q[1]为j=0代表的直线
	for i=1..n
		while l+1<=r and c(i)>q[l],q[r]交点的x坐标
			l++
		line lnew=i //决策点所代表的直线A(i)+B(i)*x
		while l+1<=r and q[r-1],q[r]交点x坐标>q[r]和lnew的交点x坐标
			r--
		q[++r]=lnew	

与刚刚的单调队列优化相比，$g(j1,j2)$ => 交点x坐标 $h(i)$ => $C(i)$

此处也可以用维护凸壳来实现

一般地，给定dp方程

$f[i]=\underset{j=1..i-1}{max}W(i,j)$

通过恒等变形，使其变成：

$W(i,j)=\frac{A(i)-B(j)}{C(i)-D(j)}$

这使得我们联想到了斜率公式

$k=\frac{\Delta y}{\Delta x}=\frac{y2-y1}{x2-x1}$

这样可以询问到一个点连到现有的点的斜率最大

• 如何维护下凸线？

  如果每次加入点的x坐标是单调增的：和上面两种方法几乎一样的单调队列写法即可维护下凸线

• 如何处理查询？

  对于给定的查询点，凸壳上的点到这个查询点的斜率是先严格单调增，（然后可能会恒等不变一段），然后再严格单调减的。

  在凸壳上使用三分法

斜率优化代码会长成这样：（其实长得跟上面的没什么区别qwq）

double slope(int a,int b)
{
	ll x1=-s[a],y1=dp1[a]-s[a]*s[a];
	ll x2=-s[b],y2=dp1[b]-s[b]*s[b];
	if(x1==x2)
	{
		return -1e18;
	}
	return (double)(y2-y1)/(x2-x1);
}

法3：二分队列

考虑一个dp方程 $dp[i]=\underset{j=1..i-1}{max}W(i,j)$

对于某两个 $j1<j2$，如果在某个 $i$ 处 $j2$ 比 $j1$ 优，那么在更大的 $i$ 处 $j2$ 也一定比 $j1$ 优。

即满足强决策单调性：一旦一个后来者超过你，他就会一直超过你，所以随着i增大，最优决策点也严格单调增

而本题满足 $h(i)>g(j1,j2)$ ，可以使用二分队列的方法进行优化

考虑：每个决策点j，是哪些i的最优决策点

对于每个 $j$，它成为最优决策点的 $i$ 要么不存在，要么一定是一段连续的区间，记为 $[l_j,r_j]$

对于 $j1<j2$，且 $[l{j1},r{j1} ]$\mathrm{和}$[l{j2},r{j2} ]$\mathrm{都}\mathrm{不}\mathrm{为}\mathrm{空}，\mathrm{那}\mathrm{么}\mathrm{有}$r{j1}<l{j2}$

所有这些 $[l_j,r_j]$ 构成了 $[1,n]$ 的一个划分

我们尝试维护当前[0,i-1]间的最优决策区间：

但是那些>=i的决策点，未来可能“抢走”当前某个j的 $[l_j,r_j]$ 的一部分，因此当前某个j的 $[l_j,r_j]$ ，只有可能变小，不可能再变大。计算i的最优决策点后，因为只需要计算i往后的，所以我们只需要保留构成[i,n]的划分的那些$[l_j,r_j]$

也就是我们将维护若干个三元组(j,l,r)

然后在队列里二分就可以找到切分点了