【洛谷4983】忘情（WQS二分+斜率优化DP）

点此看题面

• 给定一个长度为(n)的序列(a)，要求你把它划分成(m)段。
• 令(sum_i)表示第(i)段的数之和，求(sum_{i=1}^m(sum_i+1)^2)的最小值。
• (mle nle10^5)

(WQS)二分

一来这种套路早就见过了，二来事先知道了这题是(WQS)二分，于是这题就变得非常水。。。

不过感觉如果像我第一次做这种题那样没想到(WQS)二分的话，还是比较棘手的。

考虑((a+b+1)^2-((a+1)^2+(b+1)^2)=2ab-1>0)，因此划分成更多段一定会更优。

因此我们二分一个额外代价(C)，然后每次转移(f)的时候附加上一个(C)，并记录(g)表示最优解划分的段数。

那么只要找到一个合适的(C)使得(g_n)恰好等于(m)就可以了。

(DP)

考虑转移方程：（(s)表示(a)的前缀和）

把右边的项拆开并且只保留和(j)有关的项得到：

所以一个转移点(j)优于(k)（(j>k)）的充要条件就是：

由于(s_j-s_k)显然为正，因此就有：

那么我们只要维护一个单调队列，然后就可以轻松斜率优化了。

(O(nlogV))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LL long long
using namespace std;
int n,m,a[N+5];
LL f[N+5];int g[N+5],q[N+5];I bool Check(Con LL& C)//斜率优化DP验证
{
	RI i,H,T;for(q[H=T=1]=0,i=1;i<=n;++i)
	{
		#define A(x) (f[x]+1LL*a[x]*a[x]-2*a[x])
		#define S(x,y) 0.5*(A(y)-A(x))/(a[y]-a[x])
		W(H^T&&S(q[H],q[H+1])<a[i]) ++H;//弹出队首的不优元素
		f[i]=f[q[H]]+1LL*(a[i]-a[q[H]]+1)*(a[i]-a[q[H]]+1)+C,g[i]=g[q[H]]+1;//转移，注意加上额外代价
		W(H^T&&S(q[T-1],q[T])>S(q[T],i)) --T;q[++T]=i;//维护斜率单调
	}return g[n]<=m;
}
int main()
{
	RI i;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",a+i),a[i]+=a[i-1];
	LL l=0,r=1e18,mid;W(l^r) Check(mid=l+r>>1)?r=mid:l=mid+1;//WQS二分
	return Check(l),printf("%lld
",f[n]-r*m),0;
}