题解：P11520 [THUPC2025 初赛] 骑行计划
_maojun_
·
·
题解
赛场上的想法感觉比较奇怪。
如果存在 (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] 全部满足的最小代价。
- 直接用 $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)$。
---
代码是赛场上随机写的。
```cpp
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]);
}
```