B - 滑雪
思路
\(定义f(i,j)为从坐标(i,j)出发的最大值\)
\(状态转移方程f(i,j) = max(f(i+dx[k],j+dy[k]))\)
\(答案为max(f(1,1),f(1,2),...,f(n,m))\)
注意
- \(维护dp顺序使得坡度更低的坐标先被计算pair<int,pii>根据X大小排序，y则保存坐标）\)
- \(判断是否偏移是否合法\)
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 110;
const int M = 1e6+10;
int n,m;
int a[N][N],f[N][N];
int dx[]={0,0,1,-1},dy[]={-1,1,0,0}; //偏移量
vector<pair<int,pii>> v;
void solve(){
int x;
cin >> n >> m;
//确保从更小坡度出发的方案已计算出
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m ; j ++ ){
cin >> a[i][j]; //需要保存地图
v.push_back({a[i][j],{i,j}});
f[i][j] = 1;
}
}
sort(v.begin(),v.end()); //注意是begin()和end()
for(int p = 0; p < n * m; p ++ ){ //注意vector是从0开始的
int i = v[p].Y.X,j = v[p].Y.Y;
int t = f[i][j]; //注意保存这个值
for(int k = 0; k < 4; k ++ ){
if(i+dx[k] <= 0 || j+dy[k] <= 0 || i+dx[k] > n || j+dy[k] > m || a[i][j] <= a[i+dx[k]][j+dy[k]])continue;
f[i][j] = max(f[i][j],t + f[i+dx[k]][j+dy[k]]); //取每个方向的最大值
}
}
int ans = 1;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m ; j ++ ){
ans = max(ans,f[i][j]);
}
}
cout << ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}