今天把采藥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;

?

}

代碼還老長。。。。。

?

總結

以上是生活随笔為你收集整理的dp问题：采药的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。