题解：P11520 [THUPC 2025 初赛] 骑行计划

· · 题解

更好的阅读体验

题目可以形式化一下。

有一个直方图，第 i 列的高度为 a_i，初始全白。你可以花费 c 的代价涂黑一个格子，或者花费 w_i 的代价，涂黑一个宽 d_i 高 t_i 的矩形（矩形的下边界要和 x 轴重合）。求涂黑整个直方图的最小代价。

区间 dp，从上往下做。设 f_{x, l, r} 表示覆盖第 l \sim r 列高度 > x 的部分的最小代价，最终答案为 f_{0, 1, n}。

那么我们可以考虑第 l 列的状况来转移。

  1. 整列一个点一个点涂黑。 f_{x, l, r} \leftarrow f_{x, l+1, r} + \max(a_l - x, 0) \cdot c
  2. 在下面框一个矩形。假设 g_{d, t} 表示可以覆盖 d \times t 的矩形的 w 最小的矩形。那么我们可以枚举框出来的矩形的长和宽。 f_{x, l, r} \leftarrow f_{j, l, l+i-1} + f_{x, l+i, r} + g_{i, j}

复杂度 O(n^5)。

我们发现，第二个转移中 f_{j, l, l+i-1} + g_{i, j} 这一部分和 r 无关，而 f_{x, l+i, r} 和 j 无关，这启发我们可以把和 j 有关的东西整理出来，用一个类似后缀最小值的东西优化。

我们直接设 h_{l, i, x} 表示 \min \limits_{j \ge x} f_{j, l, l+i-1} + g_{i, j}，那么我们就不用枚举 j 了。所以第二个转移可以变成

f_{x, l, r} \leftarrow h_{l, i, x+1} + f_{x, l+i, r}

然后这道题就做完了，复杂度 O(n^4)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 156
using namespace std;
template <typename T> inline void chkmax(T &x,T y){x=x<y?y:x;}
template <typename T> inline void chkmin(T &x,T y){x=x<y?x:y;}
int n,m,c,mx,a[N],w[N],d[N],t[N],g[N][N],f[N][N][N],h[N][N][N];
main()
{
    scanf("%lld%lld%lld",&n,&m,&c);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)f[i][j][k]=g[j][k]=h[i][j][k]=1e15;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),chkmax(mx,a[i]);
    for(int i=1,d,t,w;i<=m;i++)
        scanf("%lld%lld%lld",&w,&d,&t),chkmin(g[d][t],w);
    for(int i=n;i;i--)
        for(int j=mx;j;j--)chkmin(g[i][j],min(g[i+1][j],g[i][j+1]));
    for(int x=0;x<N;x++)
        for(int i=0;i<=n;i++)f[x][i+1][i]=0;
    for(int x=mx;~x;x--)
        for(int l=n;l;l--)
        {
            for(int r=l;r<=n;r++)
            {
                chkmin(f[x][l][r],f[x][l+1][r]+max(0ll,a[l]-x)*c);
                for(int i=1;i<=r-l+1;i++)
                    chkmin(f[x][l][r],h[l][i][x+1]+f[x][l+i][r]);
            }
            for(int i=1;i<=n-l+1;i++)
                h[l][i][x]=min(f[x][l][l+i-1]+g[i][x],h[l][i][x+1]);
        }
    printf("%lld\n",f[0][1][n]);
    return 0;
}