Apple Catching.(POJ-2385)

浏览数：40 / 时间：2015年06月11日

一道经典的DP，算是接触的第一道吧，说说我的体会吧。

做动归题的关键就是写状态转移方程，关键是要找到可以枚举的量，也就是说这个dp数组里的下标代表的是什么。并且要具有唯一性。

通常是枚举状态，对一个状态枚举出当前最佳状态。

不过不同层次的状态如何转移的还不是很清楚，以后多做题，多理解，相互印证吧。

这道题的状态转移方程就是： dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]); i表示第i分钟，j表示走动了j次。这个方程表示当前这个状态取决于他上一分钟是如何决策的，只有两种情况，走动或者不走动。所以取之前那个状态的最大值。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int t,w;
int a[1005];
int dp[1005][50];
int main() {
    scanf("%d%d",&t,&w);
    for(int i=1;i<=t;i++)
        scanf("%d",&a[i]);
    if(a[1] == 1) {
        dp[1][0] = 1;
        dp[1][1] = 0;
    }
    if(a[1] == 2) {
        dp[1][0] = 0;
        dp[1][1] = 1;
    }
    for(int i=2;i<=t;i++)
    for(int j=0;j<=w;j++) {
        dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]);
        if((a[i]-1)==(j%2)) {
            dp[i][j]++;
        }
    }
    int maxn = -1;
    for(int i=0;i<=w;i++)
        if(maxn<dp[t][i]) maxn = dp[t][i];
    printf("%d\n",maxn);
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Apple Catching.(POJ-2385)