一共有 2 棵蘋(píng)果樹(shù)，
一頭奶牛站在其中一棵蘋(píng)果樹(shù)下等待蘋(píng)果落下，
由于任意一個(gè)時(shí)刻只能站在一棵樹(shù)下，它從一棵樹(shù)移動(dòng)到另外一棵樹(shù)的時(shí)間不計(jì)，

奶牛不愿意太頻繁移動(dòng)，現(xiàn)在給定蘋(píng)果的下落次序和最大移動(dòng)次數(shù)，問(wèn)奶牛最多可以抓住幾個(gè)蘋(píng)果。

/*16ms,388KB*/#include<cstdio> #include<algorithm> using namespace std;int dp[31];///dp[i]表示進(jìn)行了i次移動(dòng)后接到(吃掉)的蘋(píng)果數(shù)的最大值 ///偶數(shù)為第一棵樹(shù)，奇數(shù)為第二棵樹(shù) ///所以開(kāi)一個(gè)一維數(shù)組就行int main() {int i, n, w, tree;scanf("%d%d", &n, &w);while (n--){scanf("%d", &tree);if (tree == 1){for (i = 2; i <= w; i += 2)///第一棵樹(shù)dp[i] = max(dp[i], dp[i - 1]) + 1;///要么不換位置，要么換位置++dp[0];///不進(jìn)行任何移動(dòng)時(shí)所能接到的蘋(píng)果數(shù)}else{for (i = 1; i <= w; i += 2)///第二棵樹(shù)dp[i] = max(dp[i], dp[i - 1]) + 1;}//for (i = 0; i <= w; ++i)//printf("%d\t", dp[i]);//putchar(10);//putchar(10);}printf("%d\n", max(dp[w - 1], dp[w]));return 0; }

給出t與w
接著t行給出1,2分別代表那分鐘是那棵樹(shù)掉落了蘋(píng)果

解題思路：每次奶牛只有兩種決策，在某一分鐘的時(shí)候轉(zhuǎn)移或者不轉(zhuǎn)移，我們只要知道前面分鐘兩者之間的最大值，繼而可以得到當(dāng)前狀態(tài)的最大值
動(dòng)態(tài)規(guī)劃設(shè)dp[T][W]代表第T分鐘的時(shí)候移動(dòng)W次的所得到的最大蘋(píng)果數(shù)
那么狀態(tài)轉(zhuǎn)移方程為:
dp[T][W] = max(dp[T-1][W] + (a[T]==W%2+1),dp[T-1][W-1]+(a[T]==W%2+1))
a[T]==W%2+1,是看當(dāng)前轉(zhuǎn)移了W次后在哪棵樹(shù)下，當(dāng)前能不能得到這個(gè)蘋(píng)果

#include <stdio.h> #include <string.h> #define MAXT 1010 #define MAXW 35int dp[MAXT][MAXW]; int a[MAXT];int main(){int t,w,i,j;while(~scanf("%d%d",&t,&w)){dp[0][0] = 0;for(i = 1;i <= t;i++){scanf("%d",&a[i]);dp[i][0] = dp[i-1][0] + (a[i]==1); //若不轉(zhuǎn)移數(shù)為0，那么i時(shí)刻內(nèi)得到的蘋(píng)果是第一棵樹(shù)掉落的蘋(píng)果總數(shù)}for(i = 1;i<=w;i++) dp[1][i] = 1; //轉(zhuǎn)移一次以上，那么第一分鐘內(nèi)的都可以得到1個(gè)蘋(píng)果for(i = 2;i <= t;i++){for(j = 1;j <= w;j++){dp[i][j] = dp[i-1][j]+(a[i]==j%2+1); //若在i分鐘的時(shí)候轉(zhuǎn)移到另一顆樹(shù)上if(dp[i][j] < dp[i-1][j-1] + (a[i]==j%2+1)){ //若在i分鐘的時(shí)候不轉(zhuǎn)移到另一顆樹(shù)上可以得到最大dp[i][j] = dp[i-1][j-1] + (a[i]==j%2+1);}}}printf("%d\n",dp[t][w]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 2385的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。