dp问题：采药

亦凉 2022-08-09 12:52 172阅读 0赞

今天把采药A了，属于dp问题，主要思路是把所有时间都存进一个数组中，数组的值对应药的价值，下标是时间，然后记忆化搜索，碰到价值高的就赋值，相比于摘花生，辰辰是一个聪明的猴子，不废话了，上代码。

Code：

\#include <iostream>

\#include <cstring>

using namespace std;

int ji\[1002\];

int main()  \{

int t,m,a,b,i,j;

while(cin>>t>>m)

\{

memset(ji,0,sizeof(ji));

for(i=1;i<=m;i++)

\{

cin>>a>>b;

if(t-a>=0)

for(j=t-a;j>=0;j--)

if(ji\[j\]+b>ji\[j+a\])

ji\[j+a\]=ji\[j\]+b;

\}

cout<<ji\[t\]<<endl;

\}

return 0;

\}

附带另一个问题，多多摘花生，这里不吐槽那猴子有多笨了，下面的数据足以说明；

2   8  8

6  0  0  0  0  0  0  0

0         0  0  0  0  0  0  8

那只猴子如果聪明的话能摘14个，笨蛋猴子只能摘8个。

Code：

\#include <iostream>

\#include <cstdlib>

using namespace std;

int main()

\{

int n;

int row, col;

int time;

cin >> n;

while (n--)

\{

cin >> row >> col >> time;

int i, j;

int curPi = 0, curPj;

int p\[51\]\[51\];

int timet = 0;

int pg = 0;

for (i = 1; i <= row; i++)

\{

for (j = 1; j <= col; j++)

\{

cin >> p*\[j\];*

\}

\}

int maxPi = 0, maxPj = 0;

while (timet <= time)

\{

int max = 0;

for (i = 1; i <= row; i++)

\{

for (j = 1; j <= col; j++)

\{

if (p*\[j\] > max)*

\{

max = p*\[j\];*

maxPi = i;

maxPj = j;

\}

\}

\}

if (max == 0)

break;

if (curPi == 0)

curPj = maxPj;

if (timet +

(abs(maxPj - curPj) + abs(maxPi - curPi) + 1 + maxPi) <= time)

\{

timet = timet + abs(maxPj - curPj) + abs(maxPi - curPi) + 1;

curPi = maxPi;

curPj = maxPj;

pg += p\[curPi\]\[curPj\];

p\[curPi\]\[curPj\] = 0;

\}

else

break;

\}

cout << pg << endl;

\}

return 0;

\}

代码还老长。。。。。

发表评论取消回复

表情：

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

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

相关阅读

相关背包模型 AcWing 423. 采药

背包模型 AcWing 423. 采药原题链接 [AcWing 423. 采药][AcWing 423.] 算法标签 DP 01背包问题思路 !

╰+哭是因爲堅強的太久メ/ 2023年09月28日 05:20/ 0 赞/ 14 阅读

相关区间dp问题

区间dp一般有以下几种类型的题目：如何将环形区间问题转换为线性dp问题如何记录方案数目区间dp与高精度的结合高维区间dp问题一般区间dp有

浅浅的花香味﹌/ 2022年09月12日 12:54/ 0 赞/ 238 阅读

相关 423 采药（零一背包问题）

1. 问题描述：辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都

绝地灬酷狼/ 2022年09月10日 13:23/ 0 赞/ 150 阅读

相关【动态规划】0-1背包与完全背包之“采药“与“疯狂的采药“

基础背包问题（0-1、完全）请见：[背包问题教程][Link 1] P1048 \[NOIP2005 普及组\] 采药 [https://www.luogu.com.c

你的名字/ 2022年09月05日 04:10/ 0 赞/ 134 阅读

相关 dp问题：采药

今天把采药A了，属于dp问题，主要思路是把所有时间都存进一个数组中，数组的值对应药的价值，下标是时间，然后记忆化搜索，碰到价值高的就赋值，相比于摘花生，辰辰是一个聪明的猴

亦凉/ 2022年08月09日 12:52/ 0 赞/ 173 阅读

相关【日常学习】【背包DP（完全背包）】洛谷1616 疯狂的采药题解

这是一道典型的完全背包题目先上题目···于是又要迎来洛谷那令人不知道说什么的霸气摘要··· 洛谷1616 疯狂的采药本题地址：[ http://www.

比眉伴天荒/ 2022年08月03日 13:51/ 0 赞/ 188 阅读

相关采药（01背包）

1753: 采药 Time Limit: 0 Sec Memory Limit: 128 MB Submit: 10 Solved: 8 \[ [Subm

缺乏、安全感/ 2022年08月02日 15:31/ 0 赞/ 149 阅读

相关 dp问题插花

You want to arrange the window of your flower shop in a most pleasant way. You have F bu

柔光的暖阳◎/ 2022年06月18日 09:50/ 0 赞/ 124 阅读

相关 NOIP 2005 采药(DP)

题目描述辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的

傷城~/ 2022年05月17日 12:58/ 0 赞/ 155 阅读

相关 P1616 疯狂的采药

题目描述 LiYuxiang是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到

r囧r小猫/ 2022年02月28日 06:46/ 0 赞/ 222 阅读