POJ 2948 Martian Mining(DP)

时间:2022-07-01 01:13:30

题目链接

题意 : n×m的矩阵,每个格子中有两种矿石,第一种矿石的的收集站在最北,第二种矿石的收集站在最西,需要在格子上安装南向北的或东向西的传送带,但是每个格子中只能装一种传送带,求最多能采多少矿。

思路 :记忆化搜索。也可以用递推

//
#include <stdio.h>
#include <string.h>
#include <iostream> using namespace std ; int yeye[][] ,blog[][] ;
int dp[][] ; int DP(int row,int col)
{
if(row < || col < ) return ;
else if(dp[row][col] != -) return dp[row][col] ;
else return dp[row][col] = max(DP(row-,col)+yeye[row][col],DP(row,col-)+blog[row][col]) ;
}
int main()
{
int n, m ;
while(~scanf("%d %d",&n,&m))
{
if(n == && m == ) break ;
for(int i = ; i < n ; i++)
for(int j = ; j < m ;j++)
scanf("%d",&yeye[i][j]) ;
for(int i = ; i < n ; i++)
for(int j = ; j < m ;j++)
scanf("%d",&blog[i][j]) ;
memset(dp,-,sizeof(dp)) ;
for(int i = ; i < n ; i++)
for(int j = ; j < m ; j++)
yeye[i][j] += yeye[i][j-] ;
for(int i = ; i < m ; i++)
for(int j = ; j < n ; j++)
blog[j][i] += blog[j-][i] ;
printf("%d\n",DP(n,m)) ;
}
return ;
}

POJ 2948 Martian Mining(DP)的更多相关文章

  1. &lpar;中等&rpar; POJ 2948 Martian Mining,DP。

    Description The NASA Space Center, Houston, is less than 200 miles from San Antonio, Texas (the site ...

  2. 【POJ 3071】 Football(DP)

    [POJ 3071] Football(DP) Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4350   Accepted ...

  3. POJ 2948 Martian Mining

    Martian Mining Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 2251 Accepted: 1367 Descri ...

  4. POJ 3858 Hurry Plotter(DP)

    Description A plotter is a vector graphics printing device that connects to a computer to print grap ...

  5. POJ - 2385 Apple Catching (dp)

    题意:有两棵树,标号为1和2,在Tmin内,每分钟都会有一个苹果从其中一棵树上落下,问最多移动M次的情况下(该人可瞬间移动),最多能吃到多少苹果.假设该人一开始在标号为1的树下. 分析: 1.dp[x ...

  6. POJ 2948 Martian Mining&lpar;DP&rpar;这是POJ第200道,居然没发现

    题目链接 两种矿石,Y和B,Y只能从从右到左,B是从下到上,每个空格只能是上下或者左右,具体看图.求左端+上端最大值. 很容易发现如果想最优,分界线一定是不下降的,分界线上面全是往上,分界线下面都是往 ...

  7. poj 2948 Martian Mining &lpar;dp&rpar;

    题目链接 完全自己想的,做了3个小时,刚开始一点思路没有,硬想了这么长时间,想了一个思路, 又修改了一下,提交本来没抱多大希望 居然1A了,感觉好激动..很高兴dp又有所长进. 题意: 一个row*c ...

  8. POJ 1260:Pearls(DP)

    http://poj.org/problem?id=1260 Pearls Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 8 ...

  9. POJ 2192 :Zipper(DP)

    http://poj.org/problem?id=2192 Zipper Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 1 ...

随机推荐

  1. 3224&colon; Tyvj 1728 普通平衡树

    Description 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相 ...

  2. NYOJ--714--Card Trick

    /* Name: NYOJ--714--Card Trick Author: shen_渊 Date: 19/04/17 19:35 Description: 早上训练的第六届河南省程序设计大赛的题, ...

  3. php数组和正则表达式的替换拆分匹配所有

    正则表达式 $s = "a1s2d3f1g5f";//echo preg_replace("/\d/","#",$s);  //替换 //$ ...

  4. Redis持久化persistence

    一.前言 由于Redis的数据都存放在内存中,如果没有配置持久化,redis重启后数据就全丢失了,于是需要开启redis的持久化功能,将数据保存到磁盘上,当redis重启后,可以从磁盘中恢复数据. R ...

  5. Python时钟,计算程序运行时间

    关于计算程序执行时间 import time def sleep(): time.sleep(2.5) def forloop(count): for i in range(count): print ...

  6. 织梦栏目判断 seotitle的小bug

    有的栏目有seotitle(中文字符),有的没有,页面显示需要把seotitle放在括号中,所以进行了以下代码: {dede:field name="seotitle" runph ...

  7. 嵌入式C编程代码优化笔记

    [优化永远是追求某种平衡而不是走极端,优化是有侧重点的,优化是一门平衡的艺术,它往往要以牺牲程序的可读性或者增加代码长度为代价] 1.选择合适的算法和数据结构 选择一种合适的数据结构很重要,如果在一堆 ...

  8. ftp的本地用户搭建

    前期的准备跟虚拟用户一样,就是配置文件不一样 修改配置文件 就是共享的都是自己的账号的家目录,然后启动服务就可以了 本地登陆的都是自己的账号密码 ftp本地的黑名单,

  9. Timesten 日常管理命令合集

    Timesten 日常管理命令合集 以下所有操作都是基于TT  11 版,早前版本本人没用过,命令是否适用我不清楚啊! 各类服务管理 一.TT的启停  停服务:  1.停止复制与cache 进程:  ...

  10. 在表单里面检查用户名是否存javascript

    function CheckUser(fn) { $.get("/Pages/Handler/CheckExistHander.ashx", { "txt_UserNo& ...