挑战练习题2.3动态规划poj2385Apple Catchingdp

题目链接:

http://poj.org/problem?id=2385

题意:

给你t，w 表示有t分钟掉苹果，你可以移动w次，求出在最大次数时最多能接到多少苹果。

题解:

dp[i][j] : 表示第i分钟 跑了j次 得到的最大值

代码:

#include <iostream> #include <cstdio> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 1e5+10; int a[maxn]; int dp[maxn][35]; int main(){ int t,w; cin >> t >> w; for(int i=1; i<=t; i++) cin >> a[i]; //dp[i][j] : 表示第i分钟 跑了j次 得到的最大值 if(a[1] == 1){ dp[1][0] = 1; dp[1][1] = 0; }else{ dp[1][0] = 0; dp[1][1] = 1; } for(int i=2; i<=t; i++){ for(int j=0; j<=w; j++){ if(j == 0) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]); if(j%2+1 == a[i]) dp[i][j]++; } } int ans = dp[t][0]; for(int i=1; i<=w; i++) ans = max(ans,dp[t][i]); cout << ans << endl; return 0; }