标签： hard

目标

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

示例 1：

输入：mat = [[3,1],[3,4]]
输出：2
解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

示例 2：

输入：mat = [[1,1],[1,1]]
输出：1
解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。 

示例 3：

输入：mat = [[3,1,6],[-9,5,7]]
输出：4
解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。  

说明：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• -10^5 <= mat[i][j] <= 10^5

思路

有一个二维矩阵，我们可以从任意元素出发到达同行或同列的任意严格大于该元素值的位置，问我们最多能访问到多少单元格。

最直接的想法就是建立一个有向无环图，然后求最大路径长度。但是建图的过程需要循环mn(m+n)次，针对每个元素判断其同行同列上严格大于的元素。显然会超时。

于是考虑使用记忆化搜索，结果测试用例 558/566 超时，这个二维数组只有一行，有 100000列，从 1~100000，我在本地测试的时候报栈溢出。

我想要将其转为迭代的形式，但是时间紧迫，简单起见对一行或一列的情况做了特殊处理，排序后去重，最后勉强通过了。

官网题解使用的是动态规划，有时间详细看一下。//todo

代码

/**
 * @date 2024-06-19 16:28
 */
public class MaxIncreasingCells2713 {

    public int maxIncreasingCells(int[][] mat) {
        int res = 0;
        int m = mat.length;
        int n = mat[0].length;
        if (m == 1) {
            res = n;
            Arrays.sort(mat[0]);
            for (int i = 1; i < n; i++) {
                if (mat[0][i] == mat[0][i - 1]) {
                    res--;
                }
            }
            return res;
        } else if (n == 1) {
            res = m;
            Arrays.sort(mat, (a, b) -> a[0] - b[0]);
            for (int i = 1; i < m; i++) {
                if (mat[i][0] == mat[i - 1][0]) {
                    res--;
                }
            }
            return res;
        }

        int l = m * n;
        // 将二维坐标映射到一维，dp记录的是从该点为起点的能移动的最大次数
        int[] dp = new int[l];
        Arrays.fill(dp, -1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, move(mat, mat[i][j], i * n + j, i, j, dp));
            }
        }
        return res;
    }

    public int move(int[][] mat, int curVal, int next, int i, int j, int[] dp) {
        int m = mat.length;
        int n = mat[0].length;
        if (dp[next] > -1) {
            return dp[next];
        } else if (dp[next] == -2) {
            return 1;
        }
        boolean noNext = true;
        for (int k = 0; k < n; k++) {
            if (mat[i][k] > curVal) {
                noNext = false;
                dp[next] = Math.max(dp[next], move(mat, mat[i][k], i * n + k, i, k, dp) + 1);
            }
        }
        for (int k = 0; k < m; k++) {
            if (mat[k][j] > curVal) {
                noNext = false;
                dp[next] = Math.max(dp[next], move(mat, mat[k][j], k * n + j, k, j, dp) + 1);
            }
        }
        if (noNext) {
            dp[next] = -2;
            return 1;
        }

        return dp[next];
    }

}

性能

目标

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories^2 计算，其中 total_profit 是子序列中所有项目的利润总和，distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

注意：数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

示例 1：

输入：items = [[3,2],[5,1],[10,1]], k = 2
输出：17
解释：
在这个例子中，我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的总利润为 3 + 10 = 13 ，子序列包含 2 种不同类别 [2,1] 。
因此，优雅度为 13 + 22 = 17 ，可以证明 17 是可以获得的最大优雅度。 

示例 2：

输入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出：19
解释：
在这个例子中，我们需要选出长度为 3 的子序列。 
其中一种方案是 items[0] = [3,1] ，items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的总利润为 3 + 2 + 5 = 10 ，子序列包含 3 种不同类别 [1, 2, 3] 。 
因此，优雅度为 10 + 32 = 19 ，可以证明 19 是可以获得的最大优雅度。

示例 3：

输入：items = [[1,1],[2,1],[3,1]], k = 3
输出：7
解释：
在这个例子中，我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 + 2 + 3 = 6，子序列包含 1 种不同类别 [1] 。
因此，最大优雅度为 6 + 12 = 7 。

说明：

• 1 <= items.length == n <= 10^5
• items[i].length == 2
• items[i][0] == profiti
• items[i][1] == categoryi
• 1 <= profiti <= 10^9
• 1 <= categoryi <= n
• 1 <= k <= n

思路

已知一个二维数组，元素为[利润, 种类]，数组子序列的优雅值定义为利润和 + 不同种类数量^2，让我们求子序列最大的优雅值是多少。

这道题没有做出来，思考方向错了。刚开始想的是使用记忆化搜索，但是后来发现问题的解不一定能够从子问题得出。即 k-1 子序列的优雅值不一定能够得到 k 子序列的优雅值。

例如：{10, 5} -> {10, 2}, {6, 1}, {9, 5}，k = 3，我们先固定第一项，然后从后面取 k 为 2 的优雅值最大子序列 {10, 2}, {9, 5}。但是与第一项结合之后，发现类别有重复的，优雅值为 29 + 4 = 33，小于取 {10, 2}, {6, 1} 得到的优雅值 26 + 9 = 35。

因此使用递归或者动态规划都是不可解的，不能转换成规模更小的子问题。 //2024.06.14 也有可能是可以解的，只不过没有找到正确的切入点。参考访问数组中的位置使分数最大

官网题解使用的是贪心算法，由于后面会对之前的贪心选择做出调整，有网友称为反悔贪心算法。

由于我们求的是优雅值，相对顺序没有影响，因此可以排序。

然后先取最大的k个值，如果其中类别有重复的，尝试用后面的不同类别替换类别重复但利润较小的，直到没有重复的即可。

这是357场周赛的最后一题，2500多分。

代码

//todo