免费馅饼【基础DP】

题目链接:HDU-1176

kuangbin带你飞【专题十二 基础DP1 】

题目描述:

都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人,所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:
在这里插入图片描述

为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)


思路:

按照动态规划的常规套路分为4步;

1.确定状态
显然,我们需要确定第k秒 在第i个位置的收益
我们发现第k秒在第i个点的收益等于前k - 1秒在(i - 1, i , i + 1)【假设三个值都处于0 - 10】三个值中取其中的一个 + 当前点的收益;
所以我们设 dp[i][j]表示第i秒当前位置在j点的最大收益
它的子问题就是在i - 1秒 与 j点相连的两个点的最大收益;
显然这满足最优子结构和无后效性
2.转移方程
因为dp[i][j]这个点 只能由 dp[i - 1][j - 1], dp[i - 1][j]和 dp[i - 1][j + 1]这三个点转移过来;
所以我们在外层循环枚举每个时间,内层枚举每个点。然后转移是由上一层的j - 1, j , j + 1取一个最优点即可;
即 dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + val[i][j]
3.边界情况与初始化
只需将0秒时,所有位置的收益初始化为0即可;
4.计算顺序
显然,我们需要dp[i][j]就需要上一层的dp[i - 1][j - 1] dp[i - 1][j] dp[i - 1][j + 1],所以我们从前往后转移即可;

PS:
由于题目给出初始点在5这个点,所以dp[1][4] = val[1][4], dp[1][5] = val[1][5], dp[1][6] = val[1][6].其他秒按顺序转移即可;

我的代码记录的最大的时间和点,算是一种常数优化吧;

代码:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define INF 0x3f3f3f3f
#define MAX_N 100010

int a[MAX_N], dp[MAX_N][20], val[MAX_N][20];

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
while(cin >> n, n)
{
memset(dp, 0, sizeof(dp));
memset(val, 0, sizeof(val));
int tmp_val, tmp_time, max_time = 0, max_val = 0, MAX = 0;
for(int i = 1; i <= n; i++)
{
cin >> tmp_val >> tmp_time;
max_time = max(max_time, tmp_time);
max_val = max(max_val, tmp_val);
val[tmp_time][tmp_val]++;
}
for(int i = 1; i <= max_time; i++)
{
if(i == 1)
{
dp[i][5] = val[i][5];
dp[i][6] = val[i][6];
dp[i][4] = val[i][4];
}
else
{
for(int j = 0; j <= max_val; j++)
{
int tmp_max = 0;
if(j - 1 >= 0)
tmp_max = max(tmp_max, dp[i - 1][j - 1]);
if(j + 1 <= max_val)
tmp_max = max(tmp_max, dp[i - 1][j + 1]);
tmp_max = max(tmp_max, dp[i - 1][j]);
dp[i][j] = tmp_max + val[i][j];
MAX = max(MAX, dp[i][j]);
}
}
}
cout << MAX << endl;
}

return 0;
}
-------------本文结束,感谢您的阅读!-------------