学步园

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

    dp[i][j], i为第几分钟，j为走了几次。则dp[i,j]=max(dp[i-1,j-1], dp[i-1][j])+(data[i]==(j%2+1)?1:0)。对data[i]==(j%2+1)?1:0，若j为奇数，则其必在2号树下，所以+1，反之+0。

code:

#include <cstdio>
using namespace std;
int dp[1005][35];
int app[1001];
int max(int a,int b){
    if(a>b)
        return a;
    return b;
}
int main(){
    int i, j,t,w;
    while(scanf("%d%d",&t,&w)!=EOF){
        dp[0][0]=0;
        for (i=1;i<=t;i++){
            scanf("%d",&app[i]);
            dp[i][0]=dp[i-1][0]+(app[i]==1?1:0);
        }
         for (j=1;j<=w;j++)
            for (i=1;i<=t;i++)
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+(app[i]==(j%2+1)?1:0);
        printf("%d\n",dp[t][w]);
    }
   return 0;}