Gym101981B Tournament 2018icpc南京B题 wqs二分+决策单调性

传送门：http://codeforces.com/gym/101981

查题解看到这题有个wqs二分，去学习了一蛤，做了道板题，再来看这题发现还不够，于是对着代码理解了好久的决策单调性。

18年寒假我做过一道一模一样的题POJ1160，没想到南京这场竟然有原题，不过那个是O(n^3)过的，这个是O(nlognlogn)才能过。

首先如果要直接DP的话，我们需要设f[i][j]表示前i个地方选j个的最小值，而wqs二分就可以解决这个问题，我们二分一个值给每个选的地方加上一个额外的代价，那么这个额外的代价越大，选的体育场越少。那么我们通过二分这个值，就可以让体育场恰好等于k个，然后答案再减去这些额外代价就是最后的答案。

接下来就是怎么在二分了这个额外代价后求dp的值，设w[i,j]为i+1到 j 中建立一个体育场，这段的的代价，那么我们肯定是建在中间更优，那么dp[j]=dp[i]+sum[i]+sum[j]-sum((i+j)/2)-sum[(i+j+1)/2].

那么如果要直接DP的话，需要求出每一个j，还要去枚举之前从哪一个 i 转移到 j 最优，是n^2的，所以我们要使用决策单调性来优化掉这个，就是说如果dp[j]是由 dp[i] 过来转移得最优 ，那么 对于 j2>j 一定是由 i2>=i 转移过来得最优，那么我们可以用一个单调队列来维护决策， q[head....tail]表示决策转移的位置，nxt[head...tail]表示每个决策最多可以影响到哪些地方。每次dp[i]算完，我们考虑吧i这个位置加入用来转移的决策，为以后的转移做准备，我们需要对q[tail-1]到n进行二分得到nxt[tail]这个位置之前到可以让q[tail-1]的转移最优,nxt[tail]就是q[tail]的转移更优了,后面的则是当前的q[tail]更优一些。即[ nxt[tail-1] ,nxt[tail] ) 由q[tail-1]转移，nxt[tail]以后则是q[tail]转移更优。 

#include<bits/stdc++.h>
#define maxl 300010
using namespace std;
 
int n,k;
long long ans;
long long dp[maxl],sum[maxl];
int q[maxl],nxt[maxl],num[maxl];
 
inline void prework()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&sum[i]);
		sum[i]+=sum[i-1];
	}
}
 
inline long long calc(int l,int r)
{
	return sum[l]+sum[r]-sum[(l+r)>>1]-sum[(l+r+1)>>1];
}
 
inline bool cmp(int i,int j,int k)
{
	long long val1=dp[i]+calc(i,k),val2=dp[j]+calc(j,k);
	if(val1==val2)
		return num[i]<num[j];
	return val1<val2;
}
 
inline int jug(long long mid)
{
	int head=1,tail=1;
	q[1]=dp[0]=0;nxt[1]=1;
	for(int i=1;i<=n;i++)
	{
		while(head<tail && nxt[head+1]<=i)
			head++;
		dp[i]=dp[q[head]]+calc(q[head],i)+mid;
		num[i]=num[q[head]]+1;
		while(head<=tail &&i<nxt[tail]&&cmp(i,q[tail],nxt[tail]))
			tail--;
		int l=nxt[tail],r=n+1,id;
		while(l+1<r)
		{
			int mid=(l+r)>>1;
			if(cmp(i,q[tail],mid))
				r=mid;
			else
				l=mid;
		}
		if(cmp(i,q[tail],l)) 
			id=l;
		else id=l+1;
		if(id<=n)
			q[++tail]=i,nxt[tail]=id;
	}
	return num[n];
}
 
inline void mainwork()
{
	long long l=0,r=sum[n]+1,mid;
	while(l+1<r)
	{
		mid=(l+r)>>1;
		if(jug(mid)<=k)
			r=mid;
		else
			l=mid;
	}
	if(jug(l)<=k)
		ans=dp[n]-k*l;
	else
	if(jug(l+1)<=k)
		ans=dp[n]-k*(l+1);
}
 
inline void print()
{
	printf("%lld\n",ans);
}
 
int main()
{
	while(~scanf("%d%d",&n,&k))
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}