Codeforces Round #642 (Div. 3) F. Decreasing Heights (dp)
#include <bits/stdc++.h>
using namespace std;
int t;
int n,m;
long long a[105][105];
int main()
{
cin >> t;
while(t--)
{
cin >> n >> m;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
a[i][j] -= (i+j-2);//减去表中的值
}
}
// for(int i = 1; i <= n; ++i){
// for(int j = 1; j <= m; ++j){
// cout << a[i][j] << " ";
// }
// cout << endl;
// }
long long ans = 1e18;
unordered_map<long long,int> book;//标记
for(int x = 1; x <= n; ++x){
for(int y = 1; y <= m; ++y){
if(book[a[x][y]])
continue;
book[a[x][y]] = 1;
long long dp[105][105];
for(int i = 1; i <= 100; ++i)
for(int j = 1; j <= 100; ++j)
dp[i][j] = 1e18;
dp[1][1] = a[1][1]-a[x][y];
if(dp[1][1]<0)
continue;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(a[i+1][j]-a[x][y]>=0)
dp[i+1][j] = min(dp[i+1][j],dp[i][j]+a[i+1][j]-a[x][y]);
if(a[i][j+1]-a[x][y]>=0)
dp[i][j+1] = min(dp[i][j+1],dp[i][j]+a[i][j+1]-a[x][y]);
}
}
// for(int i = 1; i <= n; ++i){
// for(int j = 1; j <= m; ++j){
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
ans = min(ans,dp[n][m]);
}
}
cout << ans << endl;
}
return 0;
}