P2690 接蘋果

題目背景

USACO

題目描述

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

輸入輸出格式

輸入格式：

第一行2個數，t和k。接下來的t行，每行一個數，代表在時刻t蘋果是從1號蘋果樹還是從2號蘋果樹上掉下來的。

輸出格式：

對於每個測試點，輸出一行，一個數，為奶牛最多接到的蘋果的數量。

輸入輸出樣例

7 2
2
1
1
2
2
1
1

6

說明

DP

感覺自己的DP有所長進了，以前連轉移方程都不會列，現在居然能過三個點。。

神奇，（不會告訴你們難度是普及-）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 int a[10001];
18 int dp[10001][31];
19 int main()
20 {
21     read(n);read(m);
22     for(int i=1;i<=n;i++)
23         read(a[i]);
24     if(a[1]==1)
25         dp[1][0]=1;
26     else dp[1][1]=1;
27     for(int i=2;i<=n;i++)
28         for(int j=0;j<=m&&j<=i;j++)
29             if(a[i]==a[i-1])// 相同不用移動
30                 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+1;
31             else // 不相同 
32                 dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]);
33     int ans=0;
34     for(int i=1;i<=m;i++)    
35         ans=max(ans,dp[n][i]);
36     printf("%d",ans);
37     return 0;

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 int a[10001];
18 int dp[10001][31];
19 int main()
20 {
21     read(n);read(m);
22     for(int i=1;i<=n;i++)
23         read(a[i]);
24 /*    if(a[1]==1)
25         dp[1][0]=1;
26     else dp[1][1]=1;*/
27     for(int i=1;i<=n;i++)
28         for(int j=0;j<=m&&j<=n;j++)
29         {
30             if(j==0)
31                 dp[i][j]=dp[i-1][j];
32             else // 相同不用移動
33                 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]);
34             if(a[i]==j%2+1)
35                 dp[i][j]++;
36         }
37             
38         //    else // 不相同 
39         //        dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]);
40     int ans=0;
41     for(int i=1;i<=m;i++)    
42         ans=max(ans,dp[n][i]);
43     printf("%d",ans);
44     return 0;
45 }