动态规划——滑雪

编程入门行业动态更新时间:2024-10-15 00:22:54

动态规划——滑雪

来源于洛谷P1434 [SHOI2002]滑雪

解题思路

本题考虑采用四个方向搜索的方式，但是值得注意的是

并不能直接从头到尾遍历数组，也不能从尾到头遍历数组，而是应该使用一个优先队列来使得先遍历值比较小的点，再遍历值比较大的点！

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define reb(i,d,n) for(int i=n;i>=d;i--)
using namespace std;
const int SIZE = 101;
int res[SIZE][SIZE];
int nums[SIZE][SIZE];struct data {int x;int y;int val;
};
int m, n;
int max_res = 0;
struct cmp {bool  operator ()  (struct data d1, struct data d2) {return d1.val>d2.val;//升序}
};
priority_queue<struct data, vector<struct data>, cmp > _index;
void solve1()
{const int xx[][2] = { {-1,0},{1,0},{0,1},{0,-1} };while (1){if (_index.empty())break;struct data temp = _index.top();_index.pop();int i = temp.x;int j = temp.y;rep(k, 0, 4){if (i + xx[k][0] >= 0 && i + xx[k][0] <= m - 1 && j + xx[k][1] >= 0 && j + xx[k][1] <= n - 1){int temp = nums[i][j] - nums[i + xx[k][0]][j + xx[k][1]];if (temp > 0)res[i][j] = max(res[i][j], res[i + xx[k][0]][j + xx[k][1]] + 1);max_res = max(max_res, res[i][j]);}}}
}int main()
{scanf("%d %d", &m, &n);memset(res, 0, sizeof(res));rep(i, 0, m)rep(j, 0, n){scanf("%d", &nums[i][j]);_index.push({ i,j,nums[i][j] });}solve1();printf("%d", max_res+1);return 0;}