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.

* Lines 2..T+1: 1 or 2: the tree that will drop an apple each minute.

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.

#include <cstdio>

#include <cstring>

#define max(a,b) ((a)>(b)?(a):(b))

using namespace std;

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}

	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}

	return x*f;

}

const int MAXN=1005;

const int MAXM=45;

int n,m;

int a[MAXN];

int f[MAXN][MAXM];

int main()

{

	n=read();m=read();

	for (int i=1;i<=n;i++) a[i]=read()-1;

	memset(f,0,sizeof(f));

	for (int i=1;i<=n;i++)

		for (int j=0;j<=m;j++)

			f[i][j]=max(f[i-1][j],f[i-1][j-1])+((j&1)==a[i]);

	int ans=0;

	for (int i=0;i<=m;i++)

		ans=max(ans,f[n][i]);

	memset(f,0,sizeof(f));

	for (int i=1;i<=n;i++)

		for (int j=0;j<=m;j++)

			f[i][j]=max(f[i-1][j],f[i-1][j-1])+((j&1)!=a[i]);

	for (int i=0;i<=m;i++)

		ans=max(ans,f[n][i]);

	printf("%d\n",ans);

	return 0;

}

解法二：

　　用一个数组$f_{i,j}$表示移动了$i$步，当前位置在第$j$棵苹果树下的时候的最多苹果数。

　　对于第$k$棵树上掉下的一个苹果，要么是之前就已经移动$i$步到了第$k$棵树并等到苹果掉下，或者是移动$i-1$步，到另一棵树下，现在赶到这棵树下。状态转移方程为：

　　　　$$f_{i,j}=max\{f_{i,j},f_{i-1,(j+1)\mod~2}\}+1$$

　　$code:$

#include <iostream>

#include <cstdio>

using namespace std;

int read()

{

  	int x=0,f=1;char c=getchar();

  	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}

  	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}

  	return x*f;

}

int n,w,come;

int a[31][2]={0};

int main()

{

    n=read();w=read();

    for(int i=1;i<=n;i++)

    {

        come=read()-1;

        for (int j=0;j<=w;j++)

        	a[j][come]=max(a[j][come]+1,a[j-1][(come+1)%2]+1);

    }

    printf("%d\n",max(a[w][0],a[w][1]));

    return 0;

}