跳转 Cnblogs。

POJ 2759 Distributing tasks/Lyk Love painting 题解

知识点

二分，DP，尺取。

分析

约定 $a_i,b_i,c_i$ 分别表示第一排树种树难度、第二排树种树难度以及一二排树种树难度的和，而 $A_i,B_i,C_i$ 分别是它们的前缀和。

首先想到有二分加 DP 决策，那么我们可以有下面集中做法。

法 1

二分答案 $lim$ 后，设出 DP 状态 $f_i$ 表示：前 $2i$ 棵树最少需要 $f_i$ 个人种。

那么很显然，在 $i$ 的转移可以是两种：

• 两排一起种：（要满足能够把每个矩形和都划分为 $\le lim$ 的）

  $$f_i \gets f_j + \lceil \frac{C_i-C_j}{lim} \rceil \\$$

• 两个都单排种：

  $$f_i \gets f_j + w_a(j+1,i) + w_b(j+1,i) \\$$

  其中 $w_a(l,r),w_b(l,r)$ 分别表示将第一和二排树 $l\sim r$ 中划分成 $\le lim$ 的块的最少数量。

那么看着复杂度就不对，考虑优化。

• 两排一起种：（要满足能够把每个矩形和都划分为 $\le lim$ 的）

  我们只要考虑将两排划分成一块 $lim$ 时的情况，也就是选最小的满足 $\lceil \frac{C_i-C_j}{lim} \rceil=1$ 的 $j$（如果没有就跳过）。

• 两个都单排种：

  我们其实可以考虑两排分别从 $i$ 按一整块划分出来的块往前跳，又发现被转移的点 $j$ 取决于跳回去后在较大位置的那个点，所以每次跳还在较大位置的那个点即可，复杂度不超过 $O(m)$。

二分开始时将每次 往前 跳 $lim$ 能到的最远的位置提前预处理出来即可。

那么这样的复杂度为 $O(nm\log_2{V})$，虽然跑不满，但是算出来还是超过了上界。

法 2

考虑更换状态，设 $f_i$ 表示：前 $i$ 个人最多能种到前 $2f_i$ 棵树。那么转移和上面差不多。

首先二分开始时将每次 往后 跳 $lim$ 能到的最远的位置提前预处理出来即可。

• 两排一起种：（要满足能够把每个矩形和都划分为 $\le lim$ 的）

  我们只要考虑将两排划分成一块 $lim$ 时的情况，只要考虑 $i\to i+1$ 即可。

• 两个都单排种：

  也是考虑两排分别从 $i$ 按一整块划分出来的块往后跳，又发现被转移的点 $j$ 取决于跳回去后在较小位置的那个点，所以每次跳还在较小位置的那个点即可，复杂度不超过 $O(m)$。

复杂度变为 $O(n\log_2{V}+m^2\log_2{V})$。

代码

法 1

int n,m,mx;
int a[N],b[N],c[N],pa[N],pb[N],pc[N];
int f[N];
ll ans;
ll A[N],B[N],C[N];

bool Check(const ll lim) {
	auto Init=[&](int *a,int *pa,ll *A) {
		pa[0]=0;
		FOR(i,1,n) {
			pa[i]=pa[i-1];
			while(A[i]-A[pa[i]]>lim)++pa[i];
		}
	};
	Init(a,pa,A),Init(b,pb,B),Init(c,pc,C),f[0]=0;
	FOR(i,1,n) {
		f[i]=pc[i]<i?f[pc[i]]+1:INF;
		int ia(i),ib(i),cnt(0);
		while(cnt<=m&&(ia||ib))ia>ib?ia=pa[ia]:ib=pb[ib],++cnt,tomin(f[i],f[max(ia,ib)]+cnt);
		if(f[i]>m)return false;
	}
	return true;
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif // Plus_Cat
	I(n,m);
	FOR(i,1,n)I(a[i]),tomax(mx,a[i]),A[i]=A[i-1]+a[i];
	FOR(i,1,n)I(b[i]),tomax(mx,b[i]),B[i]=B[i-1]+b[i];
	FOR(i,1,n)c[i]=a[i]+b[i],C[i]=C[i-1]+c[i];
	for(ll l(mx),r(C[n]),mid((l+r)>>1); l<=r; mid=(l+r)>>1)Check(mid)?ans=mid,r=mid-1:l=mid+1;
	O(ans,'\n');
	return 0;
}

法 2

int n,m,mx;
int a[N],b[N],c[N],pa[N],pb[N],pc[N];
int f[M];
ll ans;
ll A[N],B[N],C[N];

bool Check(const ll lim) {
	//Init
	pa[n]=n,pb[n]=n,pc[n]=n;
	DOR(i,n-1,0) {
		pa[i]=pa[i+1],pb[i]=pb[i+1],pc[i]=pc[i+1];
		while(A[pa[i]]-A[i]>lim)--pa[i];
		while(B[pb[i]]-B[i]>lim)--pb[i];
		while(C[pc[i]]-C[i]>lim)--pc[i];
	}
	//DP
	RCL(f,0,int,m+1);
	FOR(i,0,m) {
		if(f[i]>=n)return true;
		//a,b
		int ia(f[i]),ib(f[i]),cnt(0);
		while(i+cnt<=m)ia<ib?ia=pa[ia]:ib=pb[ib],++cnt,tomax(f[i+cnt],min(ia,ib));
		//c
		tomax(f[i+1],pc[f[i]]);
	}
	return f[m]>=n;
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif // Plus_Cat
	I(n,m);
	FOR(i,1,n)I(a[i]),tomax(mx,a[i]),A[i]=A[i-1]+a[i];
	FOR(i,1,n)I(b[i]),tomax(mx,b[i]),B[i]=B[i-1]+b[i];
	FOR(i,1,n)c[i]=a[i]+b[i],C[i]=C[i-1]+c[i];
	if(m==1)return O(C[n],'\n'),0;
	for(ll l(mx),r(C[n]),mid((l+r)>>1); l<=r; mid=(l+r)>>1)Check(mid)?ans=mid,r=mid-1:l=mid+1;
	O(ans,'\n');
	return 0;
}