本文共 1139 字，大约阅读时间需要 3 分钟。
1 /* 2 题意： 有两棵苹果树，每一棵苹果树每一秒间隔的掉落下来一个苹果，一个人在树下接住苹果，不让苹果掉落！ 3 人在两棵树之间的移动是很快的！但是这个人移动的次数是有限制的，问最多可以接住多少个苹果！ 4 5 思路：dp[i][j]表示的是前 i个苹果掉落之后， 移动次数是j的情况下的最多接住的苹果的个数！ 6 7 那么dp[i][j]=max(dp[i-1][j], dp[i][j-1]) + a[i]==j%2+1 ? 1 : 0; 8 9 a[i]==j%2+1 表明第j次移动恰好移动到 第 a[i]棵苹果树下，此时这棵苹果树这号掉落下了苹果，正好接住！ 10 */11 #include12 #include 13 #include 14 #include 15 #define M 100516 using namespace std;17 18 int dp[M][35];19 20 int n, m;21 int a[M];22 23 int main(){24 scanf("%d%d", &n, &m);25 for(int i=1; i<=n; ++i)26 scanf("%d", &a[i]);27 if(a[1]==1) dp[1][0]+=1;28 for(int i=2; i<=n; ++i){29 dp[i][0]=dp[i-1][0];30 if(a[i]==1)31 dp[i][0]+=1;32 }33 34 for(int j=1; j<=m; ++j)35 for(int i=j; i<=n; ++i){36 dp[i][j]=max(dp[i][j-1], dp[i-1][j]);37 int cc=j%2+1;38 if(a[i]==cc)39 dp[i][j]+=1;40 } 41 printf("%d\n", dp[n][m]);42 return 0;43 }