更差的阅读体验
题目可以形式化一下。
有一个直方图，第 \(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\) 列的状况来转移。
- 整列一个点一个点涂黑。
\[f_{x, l, r} \leftarrow f_{x, l+1, r} + \max(a_l - x, 0) \cdot c
\]
- 在下面框一个矩形。假设 \(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;
}