题目链接：http://poj.org/problem?id=3669 题意：有一场流星雨要降临，有个倒霉鬼要躲避流星雨。给出流星雨的降落位置和时间，每一个流星雨降临会造成上下左右的附加伤害，流行砸到过的地方不能再去。这个倒霉鬼以每秒一个距离单位的速度可以向上下左右四个方向逃跑，求他能不能逃掉。不能输出-1，能的话输出最短时间。 题解：BFS。用时间来初始化状态数组，进行BFS的时候判断一下时

题目新颖，解法也是比较难想的。 题目： Bessie听说有场史无前例的流星雨即将来临；有谶言：陨星将落，徒留灰烬。为保生机，她誓将找寻安全之所（永避星坠之地）。目前她正在平面坐标系的原点放牧，打算在群星断其生路前转移至安全地点。 此次共有M (1 ≤ M ≤ 50,000)颗流星来袭，流星i将在时间点Ti (0 ≤ Ti  ≤ 1,000) 袭击点 (Xi, Yi) (0 ≤ Xi ≤ 30

题目链接 这道题琢磨了好久，首先它要对 h进行降序排列 对 w进行 升序排列然后推出 dp 方程为 dp[i][j]=min(dp[k][j-1]+s[i].w*s[k+1].h) 推导 斜率方程 就是 k2 < k 使得 dp[k][j-1]+s[i].w*s[k+1].h < dp[k2][j-1]+s[i].w*s[k2+1].h; 移项得 dp[k][j-1]-dp[k2][j-1

问题分析 首先，如果一个人的\(w\)和\(h\)均小于另一个人，那么这个人显然可以被省略。如果我们将剩下的人按\(w[i]\)递增排序，那么\(h[i]\)就是递减。 之后我们考虑DP。 我们设\(f[i][j]\)为到第\(i\)个人，打了\(j\)个洞的花费。于是我们可以得到如下DP过程： for( LL i = 1; i <= N; ++i ) F[ i ][ 1 ] = w[ i ]

我真是傻逼 这么简单的一个bfs我都不会写了。。 今天傻逼了一天； 这个题目开始不会写bfs了，后来神奇的超时，然后又是wa 超时是因为没有处理走过的路程，就是走过的路再走一遍，那样会有不必要的循环，甚至得出错误答案； 但是这不是最气的，最气的是，我的错误原因是因为INF的值写错了 ，我自己改了一个#define INF 0x7f  也就是121  而事实上应该是#define IN