Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:简单DP 附代码

Posted by X2012302616 at 2014-07-17 11:13:18 on Problem 2385
In Reply To:简单DP 附代码 Posted by:351200 at 2011-08-30 19:27:08
```> #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;
> }
>
```

Followed by: