动态规划基础练习

我们需要先从数组较大的开始进行处理，每次考察上下左右的，比较当前存储的最大值和转移来的值，哪一个大一点

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;int n, m;
int a[105][105];
int addx[] = { 0,0,1,-1 };
int addy[] = { 1,-1,0,0 };struct node
{int va;int x, y;bool operator<(node b) {return va > b.va;}
}sto[10010];int dp[105][105];int main() {cin >> n >> m;int cnt = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];sto[cnt].va = a[i][j];sto[cnt].x = i;sto[cnt].y = j; cnt++;}}sort(sto, sto + cnt);for (int i = 0; i < cnt; i++) {int now = sto[i].va;int x = sto[i].x;int y = sto[i].y;for (int i = 0; i < 4; i++) {int xx = x + addx[i];int yy = y + addy[i];if (xx<0 || yy <0 || xx>n || yy>m) continue;if (now > a[xx][yy]) dp[xx][yy] = max(dp[xx][yy],dp[x][y]+1);}}int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {ans = max(ans, dp[i][j]);}}cout << ans+1;return 0;
}