初学A*算法求解静态地图的最短路径
以前所接触过的最短路径算法是dijkstra或floyd之类的，都是在已知每两点之间距离的情况下求最短路的。那么想一下这样的案例 给你一个地图，类似于迷宫一样，中间有些障碍物，再给定起点终点，求该两点间最短路，显然，上述两种算法就不适用了，因为提到的迷宫，我们可能会很容易想到广搜bfs，但一次...
51Nod 1022 石子归并 V2 (划分型dp四边形不等式优化)
石子归并以前做过好几次，是经典划分型dp题之一，一直用的O(n3)的正常dp方法，也从未想过该怎么去优化它。 直到昨天做这道题，n的范围由往常的100改为了1000，老方法一直超时，苦不堪言，搜到有个四边形不等式的优化方法，看帖子，画式子，拉着学长帮忙推导，总算是大概弄明白了一点。 dp(i,j...
51Nod 1459 迷宫游戏
题目链接：迷宫游戏题目 你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，你就可以得到这个分数。还有若干双向道路连结这些房间，你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间，你首要目标是从起点尽快到达终点，在满足首要目标的前...
[kuangbin带你飞]专题十二 基础DP1 G - 免费馅饼(HDU 1176)
思路 很基本的dp，由于初始状态只能在位置5，所以可以倒着dp，即从时间T到0。 状态转移方程 v[i][j] = max(v[i+1][j+1], v[i][j+1], v[i-1][j+1]) / i为当前位置/ j为当前时间/ v[i][j]为接到的馅饼量 v[0][5]便为最终结果
[kuangbin带你飞]专题二 搜索进阶 C - 哈密顿绕行世界问题(HDU 2181)
题目链接：哈密顿绕行世界问题(HDU 2181)思路 起点和终点相同的dfs 代码#include #include #include #include #includ...
UVA - 12108 Extraordinarily Tired Students(特别困的学生)
题目链接UVA - 12108题目思路： 用f[i]来纪录每个学生当前的状态(是否睡觉) 用now[i]来纪录每个学生处于当前状态的总时间 用first[i]来纪录所有学生最初时处于第几分钟，用于循环中判断是否无解(若后面重复到此状态即为无解) 特殊点： 学生...
[kuangbin带你飞]专题二 搜索进阶 I - A计划(HDU 2102)
题目链接I - A计划 思路： 还是正常的bfs,多了一层而已。在移动时，增加判断，如果下一步为时光传输机且对应的节点为空地，则加入队列，否则continue即可。 代码：#include #include #include ...
UVA 1590 IP Networks（IP 网络）
题目链接：UVA - 1590 IP Networks题目大意： 一个网络地址A和一个子网掩码可以描述一个子网，子网是一个数包含32个二进制位，前n个位为1，后32－n个位为0，如：255.255.255.48(11111111|11111111|11111111|11111000) 表示某个i...
UVA - 253 Cube painting(骰子涂色)
题目链接：UVA - 253 Cube painting题目大意： 输入两个骰子，判断两个骰子是否等价，每个骰子用6个字母表示，例如 123456， 顺序为上前左右后下。思路： 任取一个面让其位于正前( 总共6个面)，然后转动上下左右四个面(转4次)，这样一个骰子的所有可能表示形式就全遍历到...
UVA - 220 Othello(黑白棋)
题目链接 说说 这种题做起来最难受了，思路上没什么难度，细节处理一大堆，一不小心就得wrong，这次还好，一气呵成，写好后稍加改动就过了。 这种题一般代码量是需要不少的，常常会有很多冗余的部分，所以在写的过程中就要怎样让接近的功能用一个函数去实现，尽力让代码充分利用，这样去想也许会多一...