自动搬运

查看原文

来自洛谷，原作者为

	lgswdn_SA 舞台少女，每日进化中

搬运于2025-08-24 22:21:56，当前版本为作者最后更新于2020-06-30 15:45:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

2022.07.05 改了一个 typo。

突然发现有这题，推荐一做。

和出题者谈话后觉得我应该要提前4年退役了。

暴力就不说了。

$\texttt{Subtask 2 }$

如果数在一个区间 $[l,r]$，我们随便选一个数 $k$，会得到这个数是否大于 $k$，并且付出 $a_k$ 的代价。复出后，我们可以得到信息：电线的长度 $x\in [l,k]$ 或者 $x\in [k+1,r]$。这不就是区间dp吗qwq，

设计状态 $f(l,r)$ 代表知道 $x\in [l,r]$ 后要多少步确定 $x$。转移方程为 $f(l,r)=\min\limits_{l\le k<r} \small \max (f(l,k),f(k+1,r))+a_k$

复杂度 $O(Tn^3)$。

namespace subtask2 {
	int f[509][509];
	void main(){
		memset(f,0x3f,sizeof(f));
		per(l,n,1) rep(r,l,n) {
			if(l==r) f[l][r]=0;
			else if(r-l==1) f[l][r]=a[l];
			else rep(k,l,r-1) f[l][r]=min(f[l][r],max(f[l][k],f[k+1][r])+a[k]);
		}
		printf("%lld\n",f[1][n]);
	}
}

$\texttt{Subtask 2 }$

这个决策 $k$ 很烦人。

把决策和答案打印出来，发现…… （大样例的样例2的第三个数据 $l=7$ 的情况，打印每一行为 l,r,决策,f[l][r]）

...
7 9 8 15
7 10 8 17
7 11 9 24
7 12 10 27
7 13 9 32
7 14 10 35
7 15 11 38
...

决策没有特别规律。

再看看式子，$\min\limits_{l\le k<r} \small \max (f(l,k),f(k+1,r))+a_k$。好像类似于 $f_x+a_x$ 的形式，有点单调队列的意思。

但是，这个 $\max$ 直接埋没了这个式子优化的潜力。所以我们直接分类讨论，看 $f(l,k)>f(k+1,r)$ 的情况和 $f(l,k)<f(k+1,r)$ 的情况。

稍微思考一下得知，由于上面打表（和思考）得知，$f(l,k)$ 随着 $k$ 的增加而增加，$f(k+1,r)$ 随着 $k$ 的增大而减小，所以 $f(l,k)-f(k+1,r)$ 是单调的，所以我们只需要找到最小的 $k$ 使得 $f(l,k)>f(k+1,r)$，即这个分界点。

现在有 3 步，找到分界点，讨论 $f(l,k)>f(k+1,r)$ 的情况和讨论 $f(l,k)<f(k+1,r)$ 的情况。

Step 1 找到分界点

这里有单调性！

对于 $f(l,x)$ 分界点是单调不降的！也就是 $f(l,r)$ 的分界点在 $f(l,r+1)$ 的左边或者相同。（傻子都能想出来？）

Step 2 计算 $f(l,k)>f(k+1,r)$ 的情况

这种情况，原式化为 $f(l,r)=\min f(l,k)+a_k$。这玩意儿是单调的，所以每次取最左端的 $k$ 即可。

Step 3 计算 $f(l,k)\le f(k+1,r)$ 的情况

这个少许麻烦了一些。原式化为 $f(l,r)=\min f(k+1,r)+a_k$。

按照最朴素的单调队列维护即可，不需要什么分类讨论。（如果单调队列不会写的，建议抛弃这道题去学习单调队列）。

namespace ac {
	int f[7009][7009],q[7009];
	void main() {
		rep(r,2,n) {
			int p=r;
			int ll=1,rr=2; q[1]=r;
			per(l,r,1) {
				if(l==r) {f[l][r]=0;continue;}
				else if(r-l==1) {f[l][r]=a[l];continue;}
				while(p>l&&f[p][r]<f[l][p-1]) p--;			//Step1
				f[l][r]=f[l][p]+a[p];						//Step2
				while(ll<rr&&q[ll]>=p) ll++;					//Step3 (and the next 3 lines)	
				if(ll<rr) f[l][r]=min(f[l][r],f[q[ll]+1][r]+a[q[ll]]);
				while(ll<rr&&f[q[rr-1]+1][r]+a[q[rr-1]]>=f[l+1][r]+a[l]) rr--;
				q[rr++]=l;
			}
		}
		printf("%lld\n",f[1][n]);
	}
}

尽管代码不长，但做的真的累。