POJ2385 Apple Catching（挑战程序设计）dp

原题链接

思路

本题就是以步数作为dp条件，如果在第一棵树下面，步数一定是偶数，如果在第二棵树下，步数一定是奇数步，那么对于每一秒苹果的下落，就给有可能在这颗树下的步数表示的状态加1，然后当前这一步可以一直站在这里不动，也可以由上一步走过来得到，那么就是取 $max(f[i?1],f[i])+1$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N];
int f[N];
int main()
{
    int n, m;while (scanf("%d%d", &n, &m) != EOF){
    memset(a, 0, sizeof a);memset(f, 0, sizeof f);for (int i = 1; i <= n; i ++ ) cin >> a[i];int res = 0; for (int i = 1; i <= n; i ++ ){
    if (a[i] == 1) {
    f[0] ++;//提前预处理0，因为0不够减1for (int j = 2; j <= m; j += 2 ){
    f[j] = max(f[j], f[j - 1]) + 1; }}else{
    for (int j = 1; j <= m; j += 2 ){
    f[j] = max(f[j], f[j - 1]) + 1; }}}for (int i = 1; i <= m; i ++ ){
    res = max(f[i], res);}cout << res << endl;}return 0;
}

总结

是一道非常简单的dp题，可是我想了好久都没有写出来，真难啊。

参考：https://blog.csdn.net/sotifish/article/details/26863921