【dp/二分+暴力】MAGRID UVALive - 5983

╰半夏微凉° 2022-06-09 14:26 155阅读 0赞

Think:  
1知识点：dp/二分+暴力  
2题意：从(1, 1)点到达(n, m)点，每经过一个点可能会失去能量或者得到能量，询问最小的出发能量使得存在一条路径，路径经过每一点时能量值大于0，已知出发点(1, 1)和终点(n, m)点可获得或者会失去能量为零  
3思路：  
1>dp:  
状态转移方程：  
(1)i == n && j == m:dp\[i\]\[j\] = 1;  
else (2)i = n: dp\[i\]\[j\] = dp\[i\]\[j+1\] - a\[i\]\[j\];  
else (3)j = m:dp\[i\]\[j\] = dp\[i+1\]\[j\] - a\[i\]\[j\];  
else (4)i != n && j != m:dp\[i\]\[j\] = max(1, min(dp\[i\]\[j+1\]-a\[i\]\[j\], dp\[i+1\]\[j\]-a\[i\]\[j\]));  
2>二分+暴力:  
已知每个点可失去的能量值小于等于1e3，n和m小于等于500，因此最大初始能量小于等于1e3\*(500+500-1)

以下为Accepted代码——方法一

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 514;
    
    int a[N][N], dp[N][N];
    
    int main(){
        int T, n, m, i, j;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            for(i = 1; i <= n; i++){
                for(j = 1; j <= m; j++){
                    scanf("%d", &a[i][j]);
                }
            }
            dp[n][m] = 1;
            for(i = m-1; i >= 1; i--)
                dp[n][i] = max(1, dp[n][i+1]-a[n][i]);
            for(i = n-1; i >= 1; i--)
                dp[i][m] = max(1, dp[i+1][m]-a[i][m]);
            for(i = n-1; i >= 1; i--){
                for(j = m-1; j >= 1; j--){
                    dp[i][j] = max(1, min(dp[i+1][j]-a[i][j], dp[i][j+1]-a[i][j]));
                }
            }
            printf("%d\n", dp[1][1]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关【暴力DP】CF1409 F

[Problem - F - Codeforces][] 题意： ![0b383875a1444f75b1163b33ac695a0b.png][] ![e01ceb20

骑猪看日落/ 2024年03月01日 07:49/ 0 赞/ 64 阅读

相关 Banks UVALive - 6855 （暴力）

![Center][] //太暴力了吧 include<cstdio> include<iostream> using namespace

素颜马尾好姑娘i/ 2024年02月18日 14:12/ 0 赞/ 57 阅读

相关 POJ 1661 暴力dp

题意略。思路：很有意思的一个题，我采用的是主动更新未知点的方式，也即刷表法来dp。我们可以把整个路径划分成横向移动和纵向移动，题目一开始就给出了Jimmy的高度，这

绝地灬酷狼/ 2023年08月17日 16:37/ 0 赞/ 132 阅读

相关 UVALive 8138-Number Generator【概率DP】

题意：随机的给你k个数，范围1~n，问你使得区间\[1, n\]的每个数都出现至少两次的期望次数。思路：f\[i\]\[j\] 表示有i个数需要出现一次，j个数需要出现两次

妖狐艹你老母/ 2023年06月12日 06:23/ 0 赞/ 24 阅读

相关 UVALive 7271-A Math Problem【二进制数位DP】

题目链接：[https://vjudge.net/problem/UVALive-7271][https_vjudge.net_problem_UVALive-7271] 题

矫情吗；*/ 2023年06月01日 06:13/ 0 赞/ 30 阅读

相关【暴力预处理+剪枝/bitset】Golf Bot UVALive - 6886

Think: 1知识点：暴力预处理+剪枝/bitset 2题意：输入n个数，查询m次，每次查询输入一个元素，判断这个元素是否可以由最初输入的n个数通过两个数相加或单独一

àì夳堔傛蜴生んèń/ 2022年06月10日 06:17/ 0 赞/ 136 阅读

相关【dp/二分+暴力】MAGRID UVALive - 5983

Think: 1知识点：dp/二分+暴力 2题意：从(1, 1)点到达(n, m)点，每经过一个点可能会失去能量或者得到能量，询问最小的出发能量使得存在一条路径，路径经

╰半夏微凉°/ 2022年06月09日 14:26/ 0 赞/ 156 阅读

相关 UVALive - 6938 区间dp+离散化

[传送门][Link 1] 思路：一条射线最小的花费就是路径上最高的那个，对于时间这个区间，我们可以将其离散化成1~600的范围，因为有三百个点，最多就600个不同的数，转移

小鱼儿/ 2022年05月17日 12:09/ 0 赞/ 171 阅读

相关 UVALive 3983 (单调队列优化dp)

题意：有一个机器人要捡n个垃圾到垃圾桶(0, 0)里，给出了机器人最多可以捡多重的垃圾c，然后给出了n个垃圾的位置和重量，机器人只能按给出的顺序捡垃圾，然后一起扔到垃圾桶里，

青旅半醒/ 2021年12月14日 04:15/ 0 赞/ 303 阅读

相关 UVALive 4015 Caves 洞穴（树形DP）

题意：一棵n个节点的有根树，树的边有正整数权，表示两个节点之间的距离，你的任务是回答这样的询问，从根节点出发，走不超过x单位的距离，最多能走多少个节点，节点经过多次算一个，对

我会带着你远行/ 2021年12月09日 04:21/ 0 赞/ 260 阅读