原题
题目分析
基础dp题,按照题意很容易给出dp定义,dp[i][j],表示在i时间内,用j次转移机会得到的最大苹果数.dp转移如下,如果j==0,则dp[i][j]=dp[i-1][j],否则 如果当前位置有苹果dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+1.否则dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]).最后在dp[T][j]里找最大值就行了,(0<=j<=W).
代码
1 #include <iostream> 2 #include <algorithm> 3 #include <utility> 4 #include <cstdio> 5 #include <cmath> 6 #include <cstring> 7 #include <string> 8 #include <vector> 9 #include <stack> 10 #include <queue> 11 #include <map> 12 #include <set> 13 14 using namespace std; 15 typedef long long LL; 16 const int INF_INT=0x3f3f3f3f; 17 const LL INF_LL=0x3f3f3f3f3f3f3f3f; 18 19 int dp[2000][100]; 20 int T[2000]; 21 22 int main() 23 { 24 // freopen("black.in","r",stdin); 25 // freopen("black.out","w",stdout); 26 int t,w; 27 cin>>t>>w; 28 for(int i=1;i<=t;i++) cin>>T[i]; 29 for(int i=1;i<=t;i++) 30 for(int j=0;j<=w;j++) 31 { 32 if(j<=i) 33 { 34 if(!j) 35 { 36 if(T[i]==1) dp[i][j]=dp[i-1][j]+1; 37 else dp[i][j]=dp[i-1][j]; 38 } 39 else 40 { 41 if(T[i]==(j&1)+1) dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+1; 42 else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]); 43 } 44 } 45 } 46 int ans=0; 47 for(int i=0;i<=w;i++) ans=max(ans,dp[t][i]); 48 cout<<ans<<endl; 49 return 0; 50 }