#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int MAXN=2002 ;
int apple[MAXN] ;
int dp[MAXN][33] ;
int Max(int x,int y)
{
    return x>y ? x:y ;
}
int main()
{
   int i,j,T,W ;
  // freopen("in.txt","r",stdin) ;
   while(cin>>T>>W)
   {
       memset(dp,0,sizeof(dp)) ;
       for(i=1 ;i<=T ;i++)
           cin>>apple[i] ;
       if(apple[1]==1)
       {
           dp[1][0]=1 ;
           dp[1][1]=0 ;
       }
       if(apple[1]==2)
       {
           dp[1][1]=1 ;
           dp[1][0]=0 ;
       }
       for(i=2 ;i<=T ;i++)
         for(j=0 ;j<=W ;j++)
         {
             if(j==0)
             {
                 dp[i][j]=dp[i-1][j]+apple[i]%2 ;
                 continue ;

             }
             dp[i][j]=Max(dp[i-1][j],dp[i-1][j-1]) ;
             if(j%2+1==apple[i])
                 dp[i][j]++ ;
         }
       int M=0 ;
       for(i=1 ;i<=W ;i++)
         M=Max(dp[T][i],M) ;
       cout<<M<<endl;
   }

    return 0;
}

• Re:简单DP 附代码 (1157) X2012302616 2014-07-17 11:13:18
  • Re:简单DP 附代码，错的！！ (0) X2012302616 2014-07-17 11:13:36
  • Re:简单DP 附代码，错的！！ (0) X2012302616 2014-07-17 11:13:42