本文共 2596 字，大约阅读时间需要 8 分钟。

题目：

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…T+1: 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.

这个题的想法是在第i时刻下判断它从一步也不走到走w步哪种方法能获得最大的苹果数。思路很简单，重要的是初始化方法。

#include <iostream>using namespace std;int dp[1010][35];int pingguo[10000];int main(){		int n, w;	cin >> n >> w;		for (int i=1; i<=n; i++)	{		cin >> pingguo[i];	}		if (pingguo[1] == 1)  		dp[1][0] = 1;	else if (pingguo[1] == 2)	{		dp[1][1] = 1;	}		for (int i=2; i<=n; i++)  	{		for (int j=0; j<=w; j++)		{  //初始化的过程			if (j == 0)			{				dp[i][j] = dp[i-1][j]+pingguo[i]%2;  //如果在步数为0的情况下，第二颗树设置为0 				continue;			}						// 状态转移方程（对他走过来和原本就在这里的苹果数比较，选择大的）			dp[i][j] = dp[i-1][j] > dp[i-1][j-1] ? dp[i-1][j]:dp[i-1][j-1];						//如果这颗树掉苹果			if (j%2+1==pingguo[i])				dp[i][j]++;		}	}		int maxnum = 0;		for (int i=0; i<=w; i++)  		maxnum = max(maxnum, dp[n][i]);		cout << maxnum << endl;		return 0;}