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

## 简单DP 附代码

Posted by 351200 at 2011-08-30 19:27:08 on Problem 2385
```#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: