bzoj 3384: [Usaco2004 Nov]Apple Catching 接蘋果，bzojusaco2004

bzoj 3384: [Usaco2004 Nov]Apple Catching 接蘋果，bzojusaco2004

雙倍經驗題。。。 -->1750

 

  dp！！

3384: [Usaco2004 Nov]Apple Catching 接蘋果

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 61  Solved: 52
[Submit][Status][Discuss]

Description

    很少有人知道奶牛愛吃蘋果．農夫約翰的農場上有兩棵蘋果樹（編號為1和2），每一棵樹上都長滿了蘋果．奶牛貝茜無法摘下樹上的蘋果，所以她只能等待蘋果從樹上落下．但是，由於蘋果掉到地上會摔爛，貝茜必須在半空中接住蘋果（沒有人愛吃摔爛的蘋果）．貝茜吃東西很快，所以她接到蘋果後僅用幾秒鐘就能吃完．每一分鐘，兩棵蘋果樹其中的一棵會掉落一個蘋果．貝茜已經過了足夠的訓練，只要站在樹下就一定能接住這棵樹上掉落的蘋果．同時，貝茜能夠在兩棵樹之間快速移動（移動時間遠少於1分鐘），因此當蘋果掉落時，她必定站在兩棵樹其中的一棵下面．此外，奶牛不願意不停地往返於兩棵樹之間，因此會錯過一些蘋果, 蘋果每分鐘掉落一個，共T(1≤T≤1000)分鐘，貝茜最多願意移動W(I≤w≤30)次．現給 出每分鐘掉落蘋果的樹的編號，要求判定貝茜能夠接住的最多蘋果數．開始時貝茜在1號樹下．

Input

    第1行：由空格隔開的兩個整數T和W.     第2到T+1行：1或2（每分鐘掉落蘋果的樹的編號）．

Output

      在貝茜移動次數不超過W的前提下她能接到的最多蘋果數

Sample Input

7 2
2
1
1
2
2
1
1

Sample Output

6

HINT

 

  7分鐘內共掉落7個蘋果一一第1個從第2棵樹上掉落，接下來的2個蘋果從第1棵樹上掉落，再接下來的2個從第2棵樹上掉落，最後2個從第1棵樹上掉落．   貝茜不移動直到接到從第1棵樹上掉落的兩個蘋果，然後移動到第2棵樹下，直到接到從第2棵

樹上掉落的兩個蘋果，最後移動到第1棵樹下，接住最後兩個從第1棵樹上掉落的蘋果．這樣貝茜共接住6個蘋果．

 

 

Source

Gold

 

#include<cstdio>
int max(int a,int b){return a>b?a:b;}
int t,w,dp[1010][33][2],n[1010],ans;
int main()
{
    scanf("%d%d",&t,&w);
    for(int i=1;i<=t;i++) scanf("%d",&n[i]);
    for(int i=1;i<=t;i++)
    {
        dp[i][0][0]=dp[i-1][0][0]+(n[i]==1);
        dp[i][0][1]=dp[i-1][0][1]+(n[i]==2);
        for(int j=1;j<=w;j++)
        {
            dp[i][j][0]=max(dp[i-1][j-1][1],dp[i-1][j][0])+(n[i]==1);
            dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j][1])+(n[i]==2);
            ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
        }
    }
    printf("%d",ans);
}