益阳网站制作公司地址,wordpress用户部门,网页设计自我介绍模板代码,企业seo顾问题意#xff1a;
给你两个数字n和m#xff1b;代表会有n个苹果掉落#xff0c;m次可以移动的机会#xff1b;有两棵树#xff0c;开始你站在树1下面#xff0c;一分钟只能移动一次#xff0c;下面的数值代表在哪一颗树下会掉落苹果#xff1b;问你在可移动的范围内
给你两个数字n和m代表会有n个苹果掉落m次可以移动的机会有两棵树开始你站在树1下面一分钟只能移动一次下面的数值代表在哪一颗树下会掉落苹果问你在可移动的范围内最多可以接到多少个苹果
题目
It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his field, each full of apples. Bessie cannot reach the apples when they are on the tree, so she must wait for them to fall. However, she must catch them in the air since the apples bruise when they hit the ground (and no one wants to eat bruised apples). Bessie is a quick eater, so an apple she does catch is eaten in just a few seconds.
Each minute, one of the two apple trees drops an apple. Bessie, having much practice, can catch an apple if she is standing under a tree from which one falls. While Bessie can walk between the two trees quickly (in much less than a minute), she can stand under only one tree at any time. Moreover, cows do not get a lot of exercise, so she is not willing to walk back and forth between the trees endlessly (and thus misses some apples).
Apples fall (one each minute) for T (1 T 1,000) minutes. Bessie is willing to walk back and forth at most W (1 W 30) times. Given which tree will drop an apple each minute, determine the maximum number of apples which Bessie can catch. Bessie starts at tree 1.
Input Line 1: Two space separated integers: T and W Lines 2…T1: 1 or 2: the tree that will drop an apple each minute.
Output
Line 1: The maximum number of apples Bessie can catch without walking more than W times.
Sample Input
7 2 2 1 1 2 2 1 1
Sample Output
6
Hint
INPUT DETAILS:
Seven apples fall - one from tree 2, then two in a row from tree 1, then two in a row from tree 2, then two in a row from tree 1. Bessie is willing to walk from one tree to the other twice.
OUTPUT DETAILS:
Bessie can catch six apples by staying under tree 1 until the first two have dropped, then moving to tree 2 for the next two, then returning back to tree 1 for the final two.
分析
(1.基础dp题,按照题意很容易看出有两个变量分钟和移动机会所以我们按照习惯写出两层for循环简单思考其中的关系就可以得到dp定义,dp[i][j]dp[i][j]dp[i][j],表示在i时间内,用 jjj次转移机会得到的最大苹果数. (2).因为开始的位置在第一棵树下那么我们就可以由移动的步数 jjj的奇偶性判断现在在哪颗树下 (3).dp转移如下,如果 j0j0j0,则 dp[i][j]dp[i−1][j]dp[i][j]dp[i-1][j]dp[i][j]dp[i−1][j],考虑j为0时到第i分钟一步都没有走动。 否则 dp[i][j]max(dp[i−1][j],dp[i−1][j−1])dp[i][j]max(dp[i-1][j],dp[i-1][j-1])dp[i][j]max(dp[i−1][j],dp[i−1][j−1]).就是当前从上一个状态下走还是不走获得苹果最多。 (4)如果现在所在的树的编号和现在掉落的苹果所在的位置相同那么接到的苹果的数量姐增加由2这个我就放在最后判断一下就行也可以放在第三步直接在推导式里面。 (5).最后在 dp[n][i]dp[n][i]dp[n][i]里找最大值就行了,(0in).(0in).(0in).表示一共走i步时n分钟吃到苹果最大值。 我今天真的闲的罗里吧嗦这么多自恋的觉得只要跟着我的思路走一定能会这道题hhh
AC模板
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int M1e310;
int n,m,ans;
int s[M],dp[M][35];
int main()
{while(~scanf(%d%d,n,m)){ans0;memset(dp,0,sizeof(dp));for(int i1; in; i)scanf(%d,s[i]);if(s[1]1)dp[1][0]1;elsedp[1][1]1;for(int i2; in; i)for(int j0; jijm; j){if(j0)//考虑j为0时也就是说到第i分钟一步都没有走动。dp[i][j]dp[i-1][j]s[i]%2;else{dp[i][j]max(dp[i-1][j],dp[i-1][j-1]);//就是当前走还是不走获得苹果最多。if(j%21s[i])//因为最开始站在树1下面可以用走多少步的奇偶来表示当前在那棵树下。dp[i][j];}}for(int i0; im; i)//表示一共走i步时n分钟吃到苹果最大值。ansmax(ans,dp[n][i]);printf(%d\n,ans);}return 0;
}
备战ccpc分站赛ing 题目分析简略见谅转载请注明出处。。。。。
