|
牛爱吃苹果是一个鲜为人知的事实。农夫约翰的田里有两棵苹果树，每棵树上都结满了苹果。贝茜够不到树上的苹果，所以她必须等着苹果掉下来。然而，她必须在空中接住它们，因为苹果落地时会碰伤(没人想吃碰伤的苹果)。贝西吃东西很快，所以她抓到的苹果几秒钟就能吃完。
每分钟，两棵苹果树中的一棵都会掉下一个苹果。贝茜很有经验，如果她站在一棵树下，苹果从树上掉下来，她就能抓住苹果。贝茜虽然能在两棵树之间很快地走(不到一分钟)，但她每次只能站在一棵树下。此外，奶牛没有得到很多锻炼，所以她不愿意在树之间无休止地来回走(因此错过了一些苹果)。
苹果(每分钟一个)落下T (1 <= T <= 1000)分钟。贝西最多愿意来回走30次。给定哪棵树每分钟会掉一个苹果，确定贝西能抓到的苹果的最大数量。贝西从第一棵树开始。
输入
*第一行:两个空格分隔的整数:T和W
*线2 . .T+1: 1或2:每分钟掉一个苹果的树。
输出
*第一行:贝西不走超过W次就能抓住的苹果的最大数量。
样例输入
7 - 2
2
1
1
2
2
1
1
样例输出
6
提示
输入详细信息:
七个苹果从树上掉下来——一个从树上2掉下来，然后两个从树上1掉下来，然后两个从树上2掉下来，然后两个从树上1掉下来。贝西愿意从一棵树走到另一棵树两次。
输出详细信息:
贝西可以在1号树下抓住6个苹果，直到头两个苹果掉下来，然后移动到2号树下接下两个，最后两个再回到1号树下。
思路：动态规划 递推式dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]); if(j%2+1 == a[i])dp[i][j]++;
#include<iostream>
#include<cstdio>
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAX 1100
#define INF 10000000
using namespace std;
int T, W;
int a[MAX];
int dp[MAX][MAX];
//dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])
void Solve(){
if(a[0] == 1){
dp[0][0] = 1;
dp[0][1] = 0;
}
else{
dp[0][0] = 0;
dp[0][1] = 1;
}
for(int i=1; i<T; i++)
for(int j=0; j<=W; j++){
if(j == 0)dp[i][j] = dp[i-1][j] + a[i]%2;
else{
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
if(j%2+1 == a[i])dp[i][j]++;
}
}
cout << dp[T-1][W] << endl;
}
//测试函数
int main(){
/*ifstream cin ("D:\\钢铁程序员\\程序数据\\044捕捉苹果.txt");//从文件读取数据流，省去手动输入的麻烦
if(!cin){//读取如果失败
cout << "ERROR" << endl;
}*/
cin >> T >> W;
for(int i=0; i<T; i++)
cin >> a[i];
Solve();
//cin.close();//打开文件以后要关闭
return 0;
}
| 
转播
