题目大意:

有个牛，好多题了，都是牛。然后她想吃苹果。有两个树，单位时间，在一棵树上会掉下来一个苹果。她必须在这个时间正好站到了这棵树下，才能吃到这个苹果。现在给你一共有T（1000）个单位时间，以及每个单位时间是哪一颗树上要掉苹果，这个牛可以瞬间从一棵树到达另一棵树下面，但是这种瞬移技能只能释放最多w（30）次 。问你这个牛最多可以吃到多少苹果。（注：牛一开始在1号树下）ps:要是问西瓜就好了，因为西瓜不长在树上···· 

思路：

设a[i][j][k]表示这个牛在第i个苹果掉下来时，在j号树下，用了k次技能，所能得到的最多的苹果数。

递推公式：a[i][j][k]=max(a[i-1][j][k],a[i-1][!j][k-1]); if(v[i]==j)a[i][j][k]++;
边界条件：a[1][j][k]；a[i][j][0]；

关于递推公式以及边界条件的解释：

这个牛在第i个苹果掉下来的时候，在第j号树下，用了k次技能。能得到这个状态的上一状态为：这个牛在第i-1个苹果掉下来的时候，在第！j号树下，用了k-1次技能；或者这个牛在第i-1个苹果掉下来的时候，在第j号树下，用了k次技能。（关键也就是这个牛在第i-1个苹果掉下来和第i个苹果掉下来之间，有没有使用技能）然后如果，这个苹果他接到了，就+1呗~

然后是关于边界条件，很适合想想一个三维的表格来储存数组a（虽然想画个三维图，但是用笔画的图烂的掉渣，估计大家也看不清，就自己想象吧），这样的话，如果要推出第i层的一个，就需要知道第i-1层的两个格（沿i轴-1的一个，以及同i-1平面内无相交边的另一个）。这样，在i取1的时候，就找不到对应的i-1平面了，所以要确定边界a[1][j][k]；同样，在k=0时就找不到对应的k-1了，所以也要确定边界a[i][j][0]。另外十分要注意，开始的时候在1号树下面，所以一切在2号数下面翻转0次得到的苹果数都是-inf。 


然后三层循环为什么从外到内的顺序为ikj:
还是有些疑问，不过目前对于这道题来看，调换ik的内外层关系并没有发生错误。对于三维图来说，只不过是改变了各个格的数值确定的顺序。然后就是对递推公式理解上就不太好解释了(其实也是可以解释的):一个一个的用技能，在第i个格用技能得到的总金额可以根据在第i-1个格用技能（a[i-1][j][k]）或者不用这个技能（a[i-1][!j][k-1]） 两种情况来确定。


#include #include #define N 1050 #define W 40 #define inf 0x3f3f3f3f using namespace std; int n; int w; bool t[N]={0}; int a[N][2][W]={0}; void input() { cin>>n>>w; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); if(x==2)t[i]=1; } } void init() { int s=0; a[0][1][0]=-inf; for(int i=1;i<=n;i++)//确定a[i][j][0] { if(t[i]==0) { s++; a[i][0][0]=s; } a[i][1][0]=-inf; //开始的时候在1号树下面，所以一切在2号数下面翻转0次得到的苹果数都是-inf } for(int k=1;k<=w;k++)//确定a[1][j][k] { for(int j=0;j<=1;j++) { if(t[1]==j) { a[1][j][k]=1; } } } } void dp() { init();//确定边界条件 for(int i=2;i<=n;i++) { for(int k=1;k<=w;k++) { for(int j=0;j<=1;j++) { a[i][j][k]=max(a[i-1][j][k],a[i-1][!j][k-1]); if(t[i]==j) { a[i][j][k]++; } } } } } int find() { int max=-inf; for(int i=0;i<=1;i++) { for(int j=0;j<=w;j++) { if(max