poj 2385 Apple Catching dp

缘起

日常浪费生命 poj 2385 Apple Catching

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
贝西这头奶牛喜欢吃苹果. FJ有2棵苹果树(标记为1和2). 贝西至多在1和2之间移动W次. 贝西一开始在1处.
贝西移动的时间和吃苹果的时间忽略不计. 每分钟这两棵苹果树中恰好有一棵会掉落苹果. 现在给定这一过程持续
的时间T以及苹果掉落的顺序（即到底是从1掉落还是从2掉落）. 求贝西最多可以接住多少个苹果?

【输入】
T（1 <= T <= 1,000）和W(1 <= W <= 30) 然后T行，每行不是1就是2表示该分钟的时候苹果从1还是从2掉落

【输出】
贝西最多接住多少苹果

【样例输入】
7 2
2
1
1
2
2
1
1

【样例输出】
6

【限制】
1s

【来源】
USACO 2004 November

网上很多人说这是经典dp（虽然我没看出来这是啥经典dp，题目做少了，QAQ）

令dp[i][j][k]是前i分钟给j次机会最后在k+1(k=0或者1)这棵苹果树时最多接住的苹果数量.

于是不难写下如下ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int t, w,dp[1005][35][2],x[1005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &t, &w);
	for (int i = 1; i<=t; i++)
	{
		scanf("%d", x+i);
	}
	int sum = 0;
	for (int i = 1; i<=t; i++)
	{
		dp[i][0][0] = dp[i-1][0][0]+ (x[i]==1); // 不给任何机会, 考虑第i分钟, 最终(因为不给任何机会, 所以其实是最初)贝西站在1
		dp[i][0][1] = 0; // 不给任何机会, 考虑第i分钟, 最终(因为不给任何机会, 所以其实是最初)贝西站在2(但是显然是办不到的, 因为你不给任何机会, 贝西怎么可能移动到2呢?)
	}
	for (int j = 1; j<=w; j++)
	{
		dp[1][j][0] = (x[1]==1); // 只考虑第一分钟, 给j次机会,最终站在1下面
		dp[1][j][1] = (x[1]==2); //只考虑第一分钟, 给j次机会, 最终站在2下面
	}
	for (int i = 2;i<=t; i++)
	{
		for (int j = 1; j<=w; j++)
		{
			dp[i][j][0] = (x[i]==1)+max(dp[i-1][j][0], dp[i-1][j-1][1]); // 分为上一步停留的树是否和当前停留的树是一棵，如果一样的话, 可以不消耗机会, 如果不一样的话, 是一定要消耗一次机会的
			dp[i][j][1] = (x[i]==2)+max(dp[i-1][j][1], dp[i-1][j-1][0]);
		}
	}
	printf("%d\n", max(dp[t][w][0], dp[t][w][1]));
	return 0;
}

ac情况

Status Accepted
Memory 232kB
Length 1021
Lang C++
Submitted 2019-08-26 11:26:37
Shared
RemoteRunId 20801616