POJ 2385 - Apple Catching

https://aibluefisher.github.io/2017/02/25/2017-03-06-POJ2385/

It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his field, each full of apples. Bessie cannot reach the apples when they are on the tree, so she must wait for them to fall. However, she must catch them in the air since the apples bruise when they hit the ground (and no one wants to eat bruised apples). Bessie is a quick eater, so an apple she does catch is eaten in just a few seconds.

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.

1.2 输入

• Line 1: Two space separated integers: T and W
• Lines 2..T+1: 1 or 2: the tree that will drop an apple each minute.

1.3 输出

Line 1: The maximum number of apples Bessie can catch without walking more than W times.

1.4 样例输入

7 2
2
1
1
2
2
1
1

1.5 样例输出

6

1.6 提示

INPUT DETAILS:

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.

2 解题思路

题目大意是有两棵苹果树，每分钟任意一棵树上会掉下苹果，可以在两棵树之间移动但移动次数有限，求如何在有限的移动次数内接到最多的苹果。
很简单的一道dp，但我还是跪了很多遍，只能说自己太弱了，dp的题还要多做。
设dp[i][j]为前i分钟移动j次以内接到的苹果数，很容易得到状态转移方程：
dp[i][j] = max(dp[i - 1][j - 1],dp[i - 1][j])，由于要接到最多的苹果，因此每次移动的目的就是为了当前可以获得更多苹果，所以当移动之后，接到的苹果数要加1，即当j % 2 + 1 == a[i]时，dp[i][j] += 1。

http://blog.csdn.net/catglory/article/details/50512221
我们设状态，dp[i][j]代表到第i分钟，转换j次，最多可以拿到多少苹果。那么就有dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 当前能否接到苹果。dp[i - 1][j]为不转换，dp[i - 1][j - 1]为转换。然后考虑转换次数的奇偶性就可以了。

1.     freopen("C:\\Users\\apple\\Desktop\\in.txt", "r", stdin);  
2.     #endif  
3.     int n, w; scanf("%d%d", &n, &w);  
4.     for (int i = 1; i <= n; ++i) {  
5.         scanf("%d", t + i);  
6.         t[i] -= 1;  
7.     }  
8.   
9.     for (int i = 1; i <= n; ++i) {  
10.         for (int j = 0; j <= w; ++j) {  
11.             if (j % 2)  
12.                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + t[i];  
13.             else  
14.                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + !t[i];  
15.         }  
16.     }  
17.   
18.     printf("%d\n", dp[n][w]);  
19.     return 0;  
20. }  

http://blog.csdn.net/u014688145/article/details/71091333

O(n)阶段，多状态问题。注意阶段和状态的区分。状态：

int[][][] dp = new int[T][W][P];

1


1

表示在第T阶段，现状态为移动了W次且在位置P处的最优解。

那么无非就是在一个阶段中30*2 = 60种状态下取最优。递推式分为四种情况：

//1. 当前不移动，且能吃到苹果 （停留在原地，为了吃苹果）
//2. 移动，且吃不到当前苹果 （为了后续最大考虑，虽然吃不到当前苹果，但没准未来是最优的选择之一）
//3. 当前不移动，且吃不到当前苹果 （同2）
//4. 移动，且能吃到苹果 （切换树，为了吃苹果）

1
2
3
4


1
2
3
4

简单来说，就是对这四种情况的状态都得存下，为了后续求解最优

static int MAX_T = 1000; //防止dp越界 static int[][][] dp = new int[MAX_T][32][2]; public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); int W = in.nextInt(); int[] nums = new int[T]; for (int i = 0; i < T; i++){ nums[i] = in.nextInt(); } // int[] nums = {2,1,1,2,2,1,1}; // int W = 2; //阶段0 移动0次 位置1时 最大值 dp[0][0][0] = nums[0] == 1 ? 1 : 0; //阶段0 移动1次 位置2时 最大值 dp[0][1][1] = nums[0] == 1 ? 0 : 1; for (int i = 1; i < nums.length; i++) { for (int j = 0; j <= W; j++) { for (int k = 1; k <= 2; k++) { if (k == nums[i]){ // not move and eat dp[i][j][k-1] = Math.max(dp[i][j][k-1], dp[i-1][j][k-1] + 1); // move and not eat dp[i][j+1][move(k)-1] = Math.max(dp[i][j+1][move(k)-1], dp[i-1][j][k-1]); }else{ // not move and not eat dp[i][j][k-1] = Math.max(dp[i][j][k-1], dp[i-1][j][k-1]); // move and eat dp[i][j+1][move(k)-1] = Math.max(dp[i][j+1][move(k)-1], dp[i-1][j][k-1]+1); } } } } System.out.println(Math.max(dp[nums.length-1][W][0],dp[nums.length-1][W][1])); } private static int move (int n){ return n == 1 ? 2 : 1; }

https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/apple_catching.html

The key to this problem is apply dynamic programming. Let denotes the maximum number of apples you can get after the th minutes and you have switched times of position. Obviously when you are in the first tree and otherwise you are in the second tree. So the iteration formular can be written as:

Under same tree means the apple trees at the same tree as the tree you will be after times of switching.

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt(), W = in.nextInt();
        int[] dp = new int[W + 1];
        for (int t = 1; t <= T; t++) {
            int tree = in.nextInt() - 1;
            for (int i = Math.min(W, t); i > 0; i--) {
                dp[i] = Math.max(dp[i] + ((i & 1) == tree ? 1 : 0), dp[i - 1] + 1);
            }
            dp[0] += (tree ^ 1);
        }
        int max = 0;
        for (int m : dp) {
            max = Math.max(max, m);
        }
        System.out.println(max);
    }

http://www.cnblogs.com/acmer-roney/archive/2012/09/21/2696613.html

先给出状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+count。

这里的dp[i][j]代表在第i分钟移动j次最多能接到的苹果数。在第i分钟奶牛到某棵树下

有两种状态：1.从另一棵树走过来(dp[i-1][j-1])2.

本来就呆在这棵树下(dp[i-1][j])。所以在第i分钟时能接到的最大苹果数就是

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+count。这里count的值可以这样计算：

如果j为偶数说明她移动了j次又回到了第一棵树下，则count=a[i]==1?1:0;

即count=2-a[i]。若j为奇数说明她移动了j次后到了第二棵树下，则count=a[i]==2?1:0

（即count=a[i]-1)。

   const int N=1005;
 6 int a[N],dp[N][35];
 7 int solve(int T,int W){
 8     int count;
 9     if(T<W)W=T;
10     for(int i=0;i<=W;i++)dp[0][i]=0;
11     for(int i=1;i<=T;i++){
12         dp[i][0]=dp[i-1][0]+2-a[i];
13         for(int j=1;j<=W&&j<=i;j++){
14             if(j%2)count=a[i]-1;
15             else   count=2-a[i];
16             dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+count;
17         }
18     }
19     count=0;
20     for(int i=0;i<=W;i++)
21         if(dp[T][i]>count)
22             count=dp[T][i];
23     return count;
24 }
25 int main()
26 {
27     int T,W;
28     while(scanf("%d %d",&T,&W)!=EOF){
29         for(int i=1;i<=T;i++)
30             scanf("%d",&a[i]);
31         printf("%d\n",solve(T,W));
32     }
33     return 0;
34 }

http://blog.acmj1991.com/?p=1171

dp[i][j]第i棵树移动第j次时能接住的最多的苹果

dp[i][j] = max(dp[i][j]+1,dp[!i][j-1])

int main()




08
{




09
    int T, W;




10
    while(~scanf("%d %d", &T, &W))




11
    {




12
        int m, ans = 0;




13
        memset(dp, -1, sizeof(dp));




14
        dp[0][0] = 0;




15
        while(T --){




16
            scanf("%d", &m);




17
            m --;




18
            for(int i = W;i >= 0; -- i)




19
            {




20
                if(dp[m][i] != -1)




21
                    dp[m][i] ++;




22
                if(dp[!m][i] != -1 && i != W)




23
                    dp[m][i + 1] = max(dp[m][i + 1], dp[!m][i] + 1);




24
            }




25
        }




26
        for(int i = 0;i <= W; ++ i){




27
            ans = max(ans, dp[0][i]);




28
            ans = max(ans, dp[1][i]);




29
        }




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




31
    }




32
}

http://www.hankcs.com/program/cpp/poj-2385-apple-catching.html
2.3 记录结果再利用的“动态规划” 基础的动态规划算法
2棵苹果树在T分钟内随机由某一棵苹果树掉下一个苹果，奶牛站在树#1下等着吃苹果，它最多愿意移动W次，问它最多能吃到几个苹果。
定义dp[x][y][z]表示第x + 1分的时候经过y次移动站在了z+1树下能吃到的最大苹果数，然后搜索所有的xyz组合，更新dp。

int tree[1000];

int dp[1000][32][2]; // dp[x][y][z]表示第x + 1分的时候经过y次移动站在了z+1树下能吃到的最大苹果数

inline int move(const int &k)

{

    return k == 0 ? 1 : 0;

}

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int T, W;

    cin >> T >> W;

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

    {

        int t;

        cin >> t;

        tree[i] = t - 1;

    }

    if (tree[0] == 0)

    {

        dp[0][0][0] = 1;

    }

    else

    {

        dp[0][1][1] = 1;

    }

    for (int i = 0; i < T - 1; ++i)

    {

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

        {

            for (int k = 0; k < 2; ++k)

            {

                if (k == tree[i + 1])

                {

                    // 下一个苹果掉在当前树下，那么下一分钟？

                    // 站着不动吃一个

                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + 1);

                    // 移动没吃到，不变

                    dp[i + 1][j + 1][move(k)] = max(dp[i + 1][j + 1][move(k)], dp[i][j][k]);

                }

                else

                {

                    // 下一个苹果掉在另一树下，那么下一分钟？

                    // 站着不动没吃到

                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);

                    // 移动吃一个

                    dp[i + 1][j + 1][move(k)] = max(dp[i + 1][j + 1][move(k)], dp[i][j][k] + 1);

                }

            }

        }

    }

    cout << *max_element(dp[T - 1][0], dp[T - 1][0] + (W + 1) * 2) << endl;

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}