力扣2713 2024.6.19

原题网址：此处为链接

个人难度评价：1700

分析：
DP顺序很重要，从大数递推到小数保证了不会每次都是最优子结构而不会有后效性。
开了个map来方便二分大于当前数的最小数，状态转移方程显然，记h[x]与l[y]表示第x行小于当前值的最优和第y列小于当前值的最优：
dp[x][y] = max(f[x], l[y])
注意h和l每次也要更新

源码：

// 2713
#include <bits/stdc++.h>
#define pp pair<int, pair<int, int>>
using namespace std;
const int INF = 0x3f3f3f3f;

class Solution {
public:

    int maxIncreasingCells(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        deque<pp> now;
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                now.push_back({-mat[i][j], {i+1, j+1}});
            }
        }
        sort(now.begin(), now.end());
        map<int, int> dph[n+1], dpl[m+1];
        int f[n+1][m+1];
        memset(f, 0 ,sizeof(f));
        int ans = 0;
        int v, x, y;
        while (now.size()){
            v = -now.front().first;
            x = now.front().second.first;
            y = now.front().second.second;
            now.pop_front();
            if (dph[x].empty()){
                f[x][y] = max(f[x][y], 1);
                dph[x][v] = 1;
            }
            else{
                f[x][y] = max(f[x][y], dph[x].upper_bound(v)->second+1);
            }
            if (dpl[y].empty()){
                f[x][y] = max(f[x][y], 1);
                dpl[y][v] = 1;
            }
            else{
                f[x][y] = max(f[x][y], dpl[y].upper_bound(v)->second+1);
            }
            dph[x][v] = max(dph[x][v], f[x][y]);
            dpl[y][v] = max(dpl[y][v], f[x][y]);
            ans = max(ans, f[x][y]);
        }
        return ans;
    }
};