这种网格图的题容易想到 dp。
考虑最普通的做法,dp[i][j]
表示走到 \((i,j)\) 处的最小代价,那么转移的时候需要确定前一个格子的高度。所以在 dp 之前,需要先定好所有格子的高度。
然后可以发现,确定所有格子的高度,其实相当于确定起点的高度。
对于某些起点的高度,可能会导致所有途径的格子都需要降低的操作。这种情况显然不可能成为最优解,因为把所有格子都抬高一格就会变得更优。也就是说,路径上经过的点,至少要有一个是没有被修改的。
所以枚举每个点作为未被修改的点进行 dp 即可,复杂度 \(O(n^2 m^2)\)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e2 + 5;
const ll inf = 1e18;
ll a[maxn][maxn];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
ll ans = inf;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
ll dis = x + y;
if (a[0][0] + dis < a[x][y]) continue;
vector<vector<ll>> dp(n, vector<ll>(m, inf));
ll start = a[x][y] - dis;
dp[0][0] = a[0][0] - start;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
ll cur = start + i + j;
if (cur > a[i][j]) continue;
if (i > 0) {
dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j] - cur);
}
if (j > 0) {
dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j] - cur);
}
}
}
ans = min(ans, dp[n - 1][m - 1]);
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
标签:39,cur,int,ll,CF,Heights,++,using,dp
From: https://www.cnblogs.com/theophania/p/p39.html