描述 有一个已知的事实，牛奶爱苹果。农夫约翰有两个苹果树（方便编号1和2）在他的领域，每个苹果。Bessie不能到达苹果，当他们在树上，所以她必须等待他们跌倒。然而，她必须赶上他们在空气中，因为苹果瘀伤当他们打地面（没有人想吃青椒苹果）。Bessie是一个快速吃的，所以一个苹果她抓住只是在几秒钟内吃。 每分钟，两个苹果树之一滴苹果。贝西，有很多练习，可以抓一个苹果，如果她站在一棵树下从一个落。虽然Bessie可以在两棵树之间快速走动（在不到一分钟的时间），她可以随时站在一棵树下。此外，牛没有得到很多的运动，所以她不愿意在树间无休止地来回走动（因此错过了一些苹果）。 苹果落下（每分钟一次）T（1 <= T <= 1,000）分钟。Bessie愿意来回走动最多W（1 <= W <= 30）次。给定哪个树将每分钟滴一个苹果，确定Bessie可以捕获的苹果的最大数量。贝西从树1开始。 输入 *行1：两个空格分隔的整数：T和W *行2..T + 1：1或2：每分钟会丢一个苹果的树。 输出 *行1：Bessie可以捕捉的最大数量的苹果，而不走超过W次。
#include <iostream> #include <cstring> //Wrong Answer using namespace std; int main() { int NUM1; int NUM2; cin>>NUM1>>NUM2; int a[NUM1]; for(int i=0;i<NUM1;i++) { cin>>a[i]; } int b[NUM1][NUM2+1]; memset(b,0,sizeof(b)); for(int i=0;i<NUM2+1;i++) { if((a[0]==1)&&(i%2==0)) { b[0][i]=1; }else if((a[0]==2)&&(i%2==1)) { b[0][i]=1; } } for(int i=1;i<NUM1;i++) { if(a[i]==1) { b[i][0]=b[i-1][0]+1; }else if(a[i]==2) { b[i][0]=b[i-1][0]+0; } } for(int i=1;i<NUM2+1;i++) { for(int j=1;j<NUM1;j++) { int max=(b[j-1][i-1]>b[j-1][i])?b[j-1][i-1]:b[j-1][i]; if(i%2==1) { if(a[j]==1) { b[j][i]=max+0; }else if(a[j]==2) { b[j][i]=max+1; } }else if(i%2==0) { if(a[j]==1) { b[j][i]=max+1; }else if(a[j]==2) { b[j][i]=max+0; } } } } /* for(int i=0;i<NUM1;i++) { for(int j=0;j<NUM2+1;j++) { cout<<b[i][j]; } cout<<endl; }*/ //cout<<b[NUM1-1][NUM2*2-1]; int max=b[NUM1-1][0]; for(int i=1;i<NUM2+1;i++) { if(b[NUM1-1][i]>max) { max=b[NUM1-1][i]; } } cout<<max; return 0; } 