题意 : 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)的更多相关文章
-
(中等) POJ 2948 Martian Mining,DP。
Description The NASA Space Center, Houston, is less than 200 miles from San Antonio, Texas (the site ...
-
【POJ 3071】 Football(DP)
[POJ 3071] Football(DP) Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4350 Accepted ...
-
POJ 2948 Martian Mining
Martian Mining Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 2251 Accepted: 1367 Descri ...
-
POJ 3858 Hurry Plotter(DP)
Description A plotter is a vector graphics printing device that connects to a computer to print grap ...
-
POJ - 2385 Apple Catching (dp)
题意:有两棵树,标号为1和2,在Tmin内,每分钟都会有一个苹果从其中一棵树上落下,问最多移动M次的情况下(该人可瞬间移动),最多能吃到多少苹果.假设该人一开始在标号为1的树下. 分析: 1.dp[x ...
-
POJ 2948 Martian Mining(DP)这是POJ第200道,居然没发现
题目链接 两种矿石,Y和B,Y只能从从右到左,B是从下到上,每个空格只能是上下或者左右,具体看图.求左端+上端最大值. 很容易发现如果想最优,分界线一定是不下降的,分界线上面全是往上,分界线下面都是往 ...
-
poj 2948 Martian Mining (dp)
题目链接 完全自己想的,做了3个小时,刚开始一点思路没有,硬想了这么长时间,想了一个思路, 又修改了一下,提交本来没抱多大希望 居然1A了,感觉好激动..很高兴dp又有所长进. 题意: 一个row*c ...
-
POJ 1260:Pearls(DP)
http://poj.org/problem?id=1260 Pearls Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8 ...
-
POJ 2192 :Zipper(DP)
http://poj.org/problem?id=2192 Zipper Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1 ...
随机推荐
-
3224: Tyvj 1728 普通平衡树
Description 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相 ...
-
NYOJ--714--Card Trick
/* Name: NYOJ--714--Card Trick Author: shen_渊 Date: 19/04/17 19:35 Description: 早上训练的第六届河南省程序设计大赛的题, ...
-
php数组和正则表达式的替换拆分匹配所有
正则表达式 $s = "a1s2d3f1g5f";//echo preg_replace("/\d/","#",$s); //替换 //$ ...
-
Redis持久化persistence
一.前言 由于Redis的数据都存放在内存中,如果没有配置持久化,redis重启后数据就全丢失了,于是需要开启redis的持久化功能,将数据保存到磁盘上,当redis重启后,可以从磁盘中恢复数据. R ...
-
Python时钟,计算程序运行时间
关于计算程序执行时间 import time def sleep(): time.sleep(2.5) def forloop(count): for i in range(count): print ...
-
织梦栏目判断 seotitle的小bug
有的栏目有seotitle(中文字符),有的没有,页面显示需要把seotitle放在括号中,所以进行了以下代码: {dede:field name="seotitle" runph ...
-
嵌入式C编程代码优化笔记
[优化永远是追求某种平衡而不是走极端,优化是有侧重点的,优化是一门平衡的艺术,它往往要以牺牲程序的可读性或者增加代码长度为代价] 1.选择合适的算法和数据结构 选择一种合适的数据结构很重要,如果在一堆 ...
-
ftp的本地用户搭建
前期的准备跟虚拟用户一样,就是配置文件不一样 修改配置文件 就是共享的都是自己的账号的家目录,然后启动服务就可以了 本地登陆的都是自己的账号密码 ftp本地的黑名单,
-
Timesten 日常管理命令合集
Timesten 日常管理命令合集 以下所有操作都是基于TT 11 版,早前版本本人没用过,命令是否适用我不清楚啊! 各类服务管理 一.TT的启停 停服务: 1.停止复制与cache 进程: ...
-
在表单里面检查用户名是否存javascript
function CheckUser(fn) { $.get("/Pages/Handler/CheckExistHander.ashx", { "txt_UserNo& ...