HDU 1176 免费馅饼(DP详细的分析)
hdu 1176原题
Problem Description
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：
0 1 2 3 4 5 6 7 8 9 10(人初始位置在5)
为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）
Input
输入数据有多组。每组数据的第一行为以正整数n(0<n<100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
Output
每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
4
思路：一道动规题。dp题一般都先用递归的思路想，因为dp的题本质上都是可以用递归解决的，只不过递归有很多缺陷，所以我们为了优化，采用dp的办法来做。既然往递归方向来想，很明显，每一步我只能往前走一步，或往后走一步，或停在原地不动只有这三种决策吧，所以大概的递归思路已经出来了，就是设一dfs函数，dfs(x,t )表示当前的位置x和当前的时刻t，所以递归方程出来了：dfs(x, t) = max(dfs(x + 1, t + 1), dfs(x - 1, t + 1), dfs(x, t + 1)) + 到达此位置能拿到的馅饼数！
所以这个时候，我们大概可以把这个题的递归版本做法写出来了：
/*
递归版本
*/
#include<iostream>
using namespace std;
struct pan{
int loc;
int time;
};
const int maxn = 100;
int n;
pan a[maxn];
int max_time;
int dfs(int x, int t)
{
//递归出口
if(t > max_time)
return 0;
//此位置能拿到的馅饼数，res
int res = 0;
for(int i = 1;i <= n;i++)
{
if(a[i].loc == x && a[i].time == t)
res++;
}
//递归搜其他的决策
if(x == 0)
return (dfs(x + 1, t + 1), dfs(x, t + 1)) + res;
else if(x == 10)
return (dfs(x - 1, t + 1), dfs(x, t + 1)) + res;
else if(x > 0 && x < 10)
{
int dp1 = dfs(x + 1, t + 1);
int dp2 = dfs(x - 1, t + 1);
int r = max(dp1, dp2);
return r + res;
}
}
int main()
{
while(scanf("%d", &n) && n != 0)
{
max_time = 0;
// Clear();
for(int i = 1;i <= n;i++)
{
scanf("%d%d", &a[i].loc, &a[i].time);
}
for(int i = 1;i <= n;i++)
{
if(a[i].time > max_time)
max_time = a[i].time;
}
cout << dfs(5, 0) << endl;
}
return 0;
}
递归版本虽然很好理解，也很方便写 ，但正如前面所说，递归效率太低了，此题如果直接提交递归版本，那么一定是超时！所以我们必须采用更为高效的动态规划算法来改写这道题。
那么我们开始第2次尝试，如何用dp算法改写这题呢？在我们用递归算法解决这道题的时候，我们其实已经将这题的状态设好了，就是dfs(x, t)，即位置和时刻两个状态的组合。一旦设好状态，剩下的事其实就好做了，就是推状态转移方程。
推状态转移方程我喜欢自己先手动的把dp数表填起来，就用题中的这个样本输入吧，这个样本的dp表应该如下图所示在填表的过程中，也证实了我们前面的递归方程是正确的，就是此题的状态转移方程！即dp[i][j] = max(dp[i - 1][j - 1], dp[i + 1][j - 1], dp[i][j - 1]) + (i, j)这个点的馅饼数
由于每一项dp[i][j]都要确保dp[i - 1][j - 1], dp[i + 1][j - 1], dp[i][j - 1]这三个量都求出才能得到，所以这一题的遍历顺序应该是先从上往下，再从左至右
那么我们就可以开始写代码了：
/*
动态规划版本
要想办法把求res的那个for循环去掉，经过思考后，无非是拿空间换时间
用二维数组应该可以
*/
#include<iostream>
using namespace std;
struct pan{
int loc;
int time;
};
const int maxn = 1000005;
int n;
pan a[maxn];
int dp[11][maxn];
int max_time;
int Max(int x, int y, int z)
{
int temp = max(x, y);
return max(temp, z);
}
int Dp()
{
//先处理边界条件，即第一个时刻
for(int l = 0;l <= 10;l++) //这里的l表示loc
{
for(int i = 1;i <= n;i++)
{
if(a[i].loc == l && a[i].time == 1)
dp[l][1] = 1;
}
}
//再来常规情况，首先要明确状态转移方程，然后明确遍历顺序才能写这部分的代码
for(int j = 2;j <= max_time;j++)
{
for(int i = 0;i <= 10;i++)
{
int res = 0;
for(int k = 1;k <= n;k++)
{
if(a[k].loc == i && a[k].time == j)
res++;
}
if(i == 0)
dp[i][j] = max(dp[i + 1][j - 1], dp[i][j - 1]) + res;
else if(i == 10)
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1]) + res;
else if(i > 0 && i < 10)
dp[i][j] = Max(dp[i][j - 1], dp[i + 1][j - 1], dp[i - 1][j - 1]) + res;
}
}
//找出dp数组中的最大值，最后将其返回
int max_res = 0;
for(int i = 0;i <= 10;i++)
{
for(int j = 1;j <= max_time;j++)
{
if(dp[i][j] > max_res)
max_res = dp[i][j];
}
}
/*
打印dp数组测试
for(int i = 0;i <= 10;i++)
{
for(int j = 1;j <= n;j++)
{
cout << dp[i][j] << " ";
}
cout << endl;
}
*/
return max_res;
}
//清理之前的dp数组残余的值
void Clear()
{
for(int i = 0;i <= 10;i++)
{
for(int j = 1;j <= max_time;j++)
{
dp[i][j] = 0;
}
}
}
int main()
{
while(scanf("%d", &n) && n != 0)
{
max_time = 0;
for(int i = 1;i <= n;i++)
{
scanf("%d%d", &a[i].loc, &a[i].time);
}
for(int i = 1;i <= n;i++)
{
if(a[i].time > max_time)
max_time = a[i].time;
}
Clear();
cout << Dp() << endl;
}
return 0;
}
但遗憾的是，这次提交还是超时，为什么呢？因为32–49行 ，我用了三重循环求解，时间复杂度成了O(n^2 * 10)， 而题中的n最大值可以到10的6次方，所以必然会超时。经过分析，三重循环中，外面两层毫无疑问需要，最后一层求res的循环可以省掉。那我们只能采取用空间换时间的方法，可以设一个二维数组来解决这个问题，就可以将res用O(1)复杂度求出，整个算法就可以降为O(10n)！
同时，这个版本还忽略了一些问题，比如输入1 2，即1位置在2时刻掉下一个馅饼，这个程序输出1个！这就错了。这里得加一个判断！
于是我的第三次代码出来了：
/*
动态规划版本
*/
#include<iostream>
#include<cmath>
using namespace std;
struct pan{
int loc;
int time;
};
const int maxn = 1000005;
int n;
pan a[maxn];
int x[12][maxn];
int dp[12][maxn];
int max_time;
int Max(int x, int y, int z)
{
int temp = max(x, y);
return max(temp, z);
}
int Dp()
{
//先处理边界条件，即第一个时刻
//此处尤为注意！因为(7, 1)和(3,1)这是不可能捡到的，所以1时刻只可能在4--6之间捡到
for(int l = 4;l <= 6;l++)
{
dp[l][1] = x[l][1];
}
//再来常规情况，首先要明确状态转移方程，然后明确遍历顺序才能写这部分的代码
for(int j = 2;j <= max_time;j++)
{
for(int i = 0;i <= 10;i++)
{
if(abs(5 - i) > j) //此处注意！如果5到它的距离无法在j时刻内走到，那就是0
{
dp[i][j] = 0;
}
else
{
int res = 0;
res = x[i][j]; //利用x数组，将这一步的时间复杂度降为O(1)!
if(i == 0)
dp[i][j] = max(dp[i + 1][j - 1], dp[i][j - 1]) + res;
else if(i == 10)
dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1]) + res;
else if(i > 0 && i < 10)
dp[i][j] = Max(dp[i + 1][j - 1], dp[i - 1][j - 1], dp[i][j - 1]) + res;
}
}
}
//找出dp数组中的最大值，最后将其返回
int max_res = 0;
for(int i = 0;i <= 10;i++)
{
for(int j = 1;j <= max_time;j++)
{
if(dp[i][j] > max_res)
max_res = dp[i][j];
}
}
//打印dp数组测试
/*for(int i = 0;i <= 10;i++)
{
for(int j = 1;j <= max_time;j++)
{
cout << dp[i][j] << " ";
}
cout << endl;
}
cout << max_time << endl;*/
return max_res;
}
//清理之前的dp数组与x数组残余的值
void Clear()
{
for(int i = 0;i <= 10;i++)
{
for(int j = 1;j <= max_time;j++)
{
dp[i][j] = 0;
x[i][j] = 0;
}
}
}
int main()
{
while(scanf("%d", &n) && n != 0)
{
max_time = 0;
for(int i = 1;i <= n;i++)
{
scanf("%d%d", &a[i].loc, &a[i].time);
}
for(int i = 1;i <= n;i++)
{
if(a[i].time > max_time)
max_time = a[i].time;
}
Clear();
for(int i = 1;i <= n;i++)
{
int lc = a[i].loc;
int te = a[i].time;
if(x[lc][te] == 0)
x[lc][te] = 1;
else
x[lc][te]++;
}
cout << Dp() << endl;
}
return 0;
}
这次终于AC了，历经磨难啊。。。
这题是很好的一个dp题，要稍微想一想，但又不至于太难，很适合刚刚进阶的选手
上一篇： HDU 1176 免费馅饼
下一篇： 用node模拟一个简单的静态服务器