自动搬运

查看原文

来自洛谷，原作者为

	maojun 猫君

搬运于2025-08-24 23:08:03，当前版本为作者最后更新于2025-01-15 14:57:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

赛场上的想法感觉比较奇怪。

如果存在 $(w',d',t')$，$w'\le w,d'\ge d,t'\ge t$，即这个操作就被偏序了，那么不妨把 $(d,t)$ 操作的代价改为 $w'$，因为如果选取的卡没有用满两个限制之一，答案不会更大。

于是可以把卡 $(w,d,t)$ 看作一个 $(d,t)$ 的权值为 $w$ 的点，在矩形上对右上角 chkmin。这样就可以在想要的地方钦定这个操作出来。

然后考虑在 $s_i$ 画成的柱状图上从上往下 dp，记 $f_{t,l,r}$ 表示考虑柱状图 $\ge t$ 的操作，区间 $[l,r]$ 全部满足的最小代价。

设辅助数组 $g_{l,r}$ 表示只考虑 $s_i$ 中 $>t$ 的部分，区间 $[l,r]$ 全部满足的最小代价。

$g$ 的转移：

• 直接用 $c$：

  $$g_{l,r}\gets g_{l,r-1}+\max\{0,a_r-t\}c$$

• 用操作。用 $\le t$ 的操作没用，所以直接从 $f_{t+1}$ 转移过来：

  $$g_{l,r}\gets\min\limits_k\{g_{l,r-k}+f_{t+1,r-k+1,r}\} $$

$f$ 的转移：

• 直接用 $c$：

  $$f_{t,l,r}\gets f_{t,l,r-1}+a_rc$$

  这条转移只在 $t=1$ 合并答案时有用，$t>1$ 时虽然没错，但显然不优。

• 用 $\ge t+1$ 的操作完成：

  $$f_{t,l,r}\gets\min\limits_k\{f_{t,l,r-k}+f_{t+1,r-k+1,r}\} $$

• 新增长度为 $k$，高度为 $t$ 的操作：

  $$f_{t,l,r}\gets\min\limits_k\{f_{t,l,r-k}+w_{k,t}+g_{r-k+1,r}\} $$

  其中 $w_{k,t}$ 就是上述后缀 $\min$ 得到的数组。表示执行长度至少为 $k$，高度至少为 $t$ 的操作的最小代价。

直接转移即可，复杂度 $O(Vn^3)$。

代码是赛场上随机写的。

typedef long long ll;
const int N=155;
int n,m,c,V=150,a[N],w[N][N];

inline void C(ll&x,ll y){x>y&&(x=y);}
ll f[N][N][N],g[N][N];
inline void main(){
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	memset(w,0x3f,sizeof w);
	for(int v,d,t;m--;){scanf("%d%d%d",&v,&d,&t);w[d][t]=min(w[d][t],v);}
	for(int i=n;i;i--)for(int j=V;j;j--)w[i][j]=min(w[i][j],min(w[i+1][j],w[i][j+1]));
	memset(f,0x3f,sizeof f);
	for(int t=V;t;t--){
		memset(g,0x3f,sizeof g);
		for(int i=1;i<=n;i++)f[t][i][i-1]=g[i][i-1]=0;
		for(int l=1;l<=n;l++)for(int r=l;r<=n;r++){
			g[l][r]=g[l][r-1]+(ll)max(0,a[r]-t)*c;
			for(int k=1;k<=r-l+1;k++)C(g[l][r],g[l][r-k]+f[t+1][r-k+1][r]);
		}
		for(int l=1;l<=n;l++)for(int r=l;r<=n;r++){
			if(t==1)f[t][l][r]=f[t][l][r-1]+(ll)a[r]*c;
			for(int k=1;k<=r-l+1;k++)
				C(f[t][l][r],f[t][l][r-k]+min(w[k][t]+g[r-k+1][r],f[t+1][r-k+1][r]));
		}
	}
	printf("%lld\n",f[1][1][n]);
}