F. Decreasing Heights
题意
给出一个n*m的矩阵 n,m<100
每个位置的值表示高度
现在从(1,1)走到(n,m);
只能走(i+1,j) or (i,j+1) 且当前所在位置的高度=要走到位置的高度-1
在出发前可以任意个位置-1高度 视为1次操作
问能使两点通路的最小操作
题解
按照题目要求
形成通路的前提条件是 存在一条路径
b0,b1,b2….bn+m-2 为了符合 b[i]+1=b[i+1]
那么这相当于第i个点 要比初始位置高出i的高度
所以原路径上所有的高度b[i]都可以转化成b[i]-i 变为可调整的高度
(对于每个点b[i]不可变化的高度是i)
则限制条件b[i]+1=b[i+1]变为b[i]=b[i+1]
那么对于b0,b1,b2….bn+m-2 这条路径需要修改的次数为
转化后求$∑b[i]-min(b[0,1,2,…,n+m-2])$;
取min操作是将路径中的最低点作为基准点
所以枚举路径中可能的最低值low On^2
再On^2 dp转移 整体On^4
参考博客
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=100+5;
ll data[Max][Max];
ll dp[Max][Max];
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>data[i][j];
data[i][j]-=(i+j-2);
}
}
ll ans=1e18;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ll low=data[i][j];
for(int r=1;r<=n;r++){
for(int c=1;c<=m;c++)dp[r][c]=1e18;
}
for(int r=1;r<=n;r++){
for(int c=1;c<=m;c++){
ll de=data[r][c]>=low?data[r][c]-low:1e18;
if(r==1&&c==1)dp[r][c]=min(dp[r][c],de);
if(r>1)dp[r][c]=min(dp[r][c],dp[r-1][c]+de);
if(c>1)dp[r][c]=min(dp[r][c],dp[r][c-1]+de);
}
}
ans=min(ans,dp[n][m]);
}
}
cout<<ans<<endl;
}
}
|