UVALive 3530 Martian Mining

川长思鸟来 2021-12-09 20:51 141阅读 0赞

## 题意：给出n\*m网格中每个格子有A，B两种矿，A矿必须从右向左运输，B矿必须从下往上运输，管子不能拐弯或者折断，要求收集到的A，B矿的总量尽量大。 ##

## 分析：每个格子不是A就是B矿的管道，只有两个选择。所以dp\[i\]\[j\]=max(dp\[i\]\[j-1\]+b\[i\]\[j\],dp\[i-1\]\[j\]+a\[i\]\[j\])，a\[i\]\[j\],b\[i\]\[j\]分别代表从右往左和从下往上运输方式的前j,前i的总矿数，做个前缀和。   代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 510;
    int a[N][N],b[N][N],dp[N][N],n,m;
    
    int main(){
        while (scanf("%d%d",&n,&m) != EOF && n+m){
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++){
                    scanf("%d",&a[i][j]);
                    a[i][j] += a[i][j-1];
                }
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++){
                    scanf("%d",&b[i][j]);
                    b[i][j] += b[i-1][j];
                }
            memset(dp,0,sizeof(dp));
            int ans = 0;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    dp[i][j] = max(dp[i-1][j]+a[i][j],dp[i][j-1]+b[i][j]);
            printf("%d\n",dp[n][m]);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 OHEM(online hard example mining)

最早由RGB在论文《Training Region-based Object Detectors with Online Hard Example Mining》中提出，用于f

ゞ浴缸里的玫瑰/ 2023年06月04日 12:51/ 0 赞/ 28 阅读

相关 hard negative mining method

A standard solution, known as hard negative mining, is to iteratively grow, or bootstrap

叁歲伎倆/ 2022年12月17日 07:24/ 0 赞/ 110 阅读

相关 UVALive 2197

题意：n个点，m条边，还有一个k，给出每条边的信息，让你选择一些边，使得这些边组成的图里面，每个点只属于k个回路上，问最小的费用。分析：如果每个点都只在k个回路上，那

布满荆棘的人生/ 2022年10月02日 12:00/ 0 赞/ 19 阅读

相关 UVALive 2965 侏罗纪

题目链接:[https://vjudge.net/problem/34853/origin][https_vjudge.net_problem_34853_origin]

清疚/ 2022年10月01日 00:39/ 0 赞/ 127 阅读

相关 poj 2920 Mine Map【BFS】

Mine Map <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS</td>

港控/mmm°/ 2022年08月17日 15:17/ 0 赞/ 152 阅读

相关 UVALive 3971 组装电脑

/\\ 你有b元钱，想要组装一台电脑。给出n个配件的种类、品质因子，和价格，每种类型的配件各买一个，总价不超过b，求配件最小品质因子的最大值。 sample

曾经终败给现在/ 2022年07月14日 15:55/ 0 赞/ 150 阅读

相关 TOJ3184 Mine sweeping dfs

3184: Mine sweeping 描述 I think most of you are using system named of xp or vista or

迷南。/ 2022年05月19日 11:14/ 0 赞/ 149 阅读

相关 The Origins of Data Mining

Data mining draws upon ideas, 1. sampling, estimation, and hypothesis testing from stat

迈不过友情╰/ 2022年03月27日 10:15/ 0 赞/ 152 阅读

相关 I - Mine Sweeper

题目描述： The game Minesweeper is played on an n by n grid. In this grid are hidden m min

亦凉/ 2022年03月20日 08:08/ 0 赞/ 205 阅读

相关 UVALive 3530 Martian Mining

题意：给出n\m网格中每个格子有A，B两种矿，A矿必须从右向左运输，B矿必须从下往上运输，管子不能拐弯或者折断，要求收集到的A，B矿的总量尽量大。分析：每个格子不是A

川长思鸟来/ 2021年12月09日 20:51/ 0 赞/ 142 阅读