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

## 交了3次AC了- -DP方面还是新手啊

Posted by Ink213 at 2013-04-18 12:46:39 on Problem 2385
```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=1222;
int dp[4][40][MAXN], ap[MAXN];
int main()
{
int t, w, i, j, k, p;
while(scanf("%d%d",&t,&w)!=EOF)
{
memset(dp,0,sizeof(dp));
for(i=1; i<=t; i++)
{
scanf("%d",&ap[i]);
}
for(i=1; i<=t; i++)
{
for(j=1; j<=2; j++)
{
if(j==1) p=2;
else p=1;
for(k=0; k<=t&&k<=w; k++)
{
if(j==ap[i])
{
dp[j][k][i]=max(dp[j][k][i-1]+1,dp[j][k][i]);
if(k<w) dp[j][k+1][i]=max(dp[p][k][i-1]+1,dp[j][k+1][i]);
}
else
{
dp[j][k][i]=max(dp[j][k][i-1],dp[j][k][i]);
if(k<w) dp[j][k+1][i]=max(dp[p][k][i-1],dp[j][k+1][i]);
}
}
}
}
int solv=0;
for(i=1; i<=2; i++)
for(j=0; j<=w; j++)
if(dp[i][j][t]>solv) solv=dp[i][j][t];
printf("%d\n",solv);
}
return 0;
}
```

Followed by: