动态规划 LIS POJ-1088 滑雪

[ POJ - 1088 ]

题目大意

求最长上升子序列的题目，二维数组稍微转化一下

题解代码

#include<bits/stdc++.h>
using namespace std;

int dp[105][105];
int h[105][105];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

struct node{ 
    int h;
    int x, y;
}s[10050];

bool cmp(node a, node b)
{
    return a.h < b.h;
}

int main(void)
{
    int n, m;
    cin >> n >> m;
    int r = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &h[i][j]);
            dp[i][j] = 1;
            s[r].h = h[i][j];
            s[r].x = i;
            s[r].y = j;
            r++;
        }
    }

    sort(s, s + r, cmp);
    int ans = 1;
    for (int i = 0; i < r; i++) {
        int lx = s[i].x;
        int ly = s[i].y;
        for (int i = 0; i < 4; i++) {
            int x = lx + dx[i];
            int y = ly + dy[i];
            if (x>=1 && y>=1 && x<=n && y<=m && h[x][y] > h[lx][ly]) {
                dp[x][y] = max(dp[x][y], dp[lx][ly] + 1);
                ans = max(ans, dp[x][y]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}