HDU 1176 DP 免费馅饼

本文主要是介绍HDU 1176 DP 免费馅饼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刚开始自己写的时候有点思路, 想着吧数据存入结构体, 然后对时间排序, 对应着去找状态方程。

可是自己怎么找也找不到, 看了http://blog.csdn.net/zxy_snow/article/details/6684937的博客,  忽然有了启发

然后自己写, 写完后觉得挺对, WA了, 之后各种改各种WA. 

回过头来想她的思路, 发现自己对某一时刻某一地点没有馅饼的DP状态没有更新, 那铁定错啦。

然后改, 还是错。。。。。 仔细一调试发现pie[i][j] 写成了pie[i][i]。。。

这是我WA的。。留下印记,, 以防下次写不知道以前是怎么错的

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int pie[100010][11], dp[100010][11];
int max3(int a, int b, int c)
{int max3 = -1;if (max3 < a) max3 = a;if (max3 < b) max3 = b;if (max3 < c) max3 = c;return max3;
}
int main()
{int n, x, t, i, j, maxt, ans, temp;while (scanf("%d", &n) && n){memset(pie, 0, sizeof(pie));memset(dp, 0, sizeof(dp));maxt = ans = -1;for (i = 0; i < n; i++){scanf("%d%d", &x, &t);pie[t][x]++;maxt = max(maxt, t);}for (i = 1; i <= maxt; i++){for (j = 0; j <= 10; j++){if (pie[i][j]){if (j == 0)dp[i][j] = max(dp[i-1][j], dp[i-1][j+1]);else if (j == 10)dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]);elsedp[i][j] = max3(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]);//if (i >= abs(j - 5))dp[i][j] += pie[i][j];ans = max(ans, dp[i][j]);}}}printf("%d\n", ans);}return 0;
}

这个是WA 7次后A掉的

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int pie[100010][11], dp[100010][11];
int max3(int a, int b, int c)
{int max3 = -1;if (max3 < a) max3 = a;if (max3 < b) max3 = b;if (max3 < c) max3 = c;return max3;
}
int main()
{int n, x, t, i, j, maxt, ans, temp;while (scanf("%d", &n) && n){memset(pie, 0, sizeof(pie));memset(dp, 0, sizeof(dp));maxt = ans = -1;//保存数据在某一时刻某一点for (i = 0; i < n; i++){scanf("%d%d", &x, &t);pie[t][x]++;maxt = max(maxt, t);}for (i = 1; i <= maxt; i++){for (j = 0; j <= 10; j++){//无论有没有馅饼都更新dp[i][j]if (j == 0)dp[i][j] = max(dp[i-1][j], dp[i-1][j+1]);else if (j == 10)dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]);elsedp[i][j] = max3(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]);//如果有馅饼并且当前时间大于我从5位置移动到该位置//即我能够接到馅饼仅考虑前5秒情况//因为只有在前5秒我某些位置的馅饼我一定接不到if (pie[i][j] && i >= abs(j - 5))dp[i][j] += pie[i][j];ans = max(ans, dp[i][j]);}}printf("%d\n", ans);}return 0;
}

这篇关于HDU 1176 DP 免费馅饼的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---