鱼C论坛

 找回密码
 立即注册
查看: 2070|回复: 1

[技术交流] C++刷LeetCode(1937. 扣分后的最大得分*****)【动态规划】【优化】

[复制链接]
发表于 2021-7-24 16:04:52 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
给你一个 m x n 的整数矩阵 points (下标从 0 开始)。一开始你的得分为 0 ,你想最大化从矩阵中得到的分数。

你的得分方式为:每一行 中选取一个格子,选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。

然而,相邻行之间被选中的格子如果隔得太远,你会失去一些得分。对于相邻行 r 和 r + 1 (其中 0 <= r < m - 1),选中坐标为 (r, c1) 和 (r + 1, c2) 的格子,你的总得分 减少 abs(c1 - c2) 。

请你返回你能得到的 最大 得分。

abs(x) 定义为:

如果 x >= 0 ,那么值为 x 。
如果 x < 0 ,那么值为 -x 。
 

示例 1:


输入:points = [[1,2,3],[1,5,1],[3,1,1]]
输出:9
解释:
蓝色格子是最优方案选中的格子,坐标分别为 (0, 2),(1, 1) 和 (2, 0) 。
你的总得分增加 3 + 5 + 3 = 11 。
但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
你的最终得分为 11 - 2 = 9 。
示例 2:


输入:points = [[1,5],[2,3],[4,2]]
输出:11
解释:
蓝色格子是最优方案选中的格子,坐标分别为 (0, 1),(1, 1) 和 (2, 0) 。
你的总得分增加 5 + 3 + 4 = 12 。
但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。
你的最终得分为 12 - 1 = 11 。
 

提示:

m == points.length
n == points[r].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= points[r][c] <= 105
通过次数2,658提交次数11,536

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-number-of-points-with-cost
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
    int m = points.size();
    int n = points[0].size();
    vector<long>pre(n);//记录上一行的值
    //由于某行的dp值只与上一行的值有关,故只需要两个long[n]的数组作为dp数组做状态转移。
    for (auto point : points) {
        vector<long>cur(n);//记录这一行的dp值
        long best = LLONG_MIN;
        //正序遍历
        //为何要正序,因为这时是在k在j左边的情况,那么max{dp[i-1][k] + k}中的k可取[0,j]
        for (int j = 0; j < n; j++) {
            best = max(best, pre[j] + j);//相当于max{dp[i-1][k] + k}的操作
            cur[j] = max(cur[j], point[j] - j + best);
        }
        best = LLONG_MIN;
        //倒序遍历
        //为何要倒序,因为这时是k在j右边的情况,那么max{dp[i-1][k] - k}中的k可取[j,n-1]
        for(int j = n-1; j >= 0; j--){
            best = max(best, pre[j] - j);//再倒序遍历,找上一行最大的dp[i-1][k]-k
            cur[j] = max(cur[j], best + point[j] + j);
        }
        pre = cur;
    }
    return *max_element(pre.begin(), pre.end());
    }
};


参考链接:https://leetcode-cn.com/problems ... n-by-leetcode-60zl/   及其中的评论

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-7-24 16:05:22 | 显示全部楼层
本帖最后由 糖逗 于 2021-7-24 18:15 编辑

好难想,这道题。看题解想了好久。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-15 07:37

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表