一.题目链接： HDU-3001 二.题目大意： n 个点，m 条双向边. 之后 m 行 每行三个整数 a，b，c 表示第 i 条边的起点，终点，权值. 要求每个点都走到且不超过两次. 求最小花费. 三.分析： 一道状压 DP 模板题 状压 DP 入门 详见代码. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include &l...

一.题目链接： HDU-3001 二.题目大意： n 个点，m 条双向边. 之后 m 行 每行三个整数 a，b，c 表示第 i 条边的起点，终点，权值. 要求每个点都走到且不超过两次. 求最小花费. 三.分析： 一道状压 DP 模板题 状压 DP 入门 详见代码. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include &l...

一.题目链接： HDU-3001 二.题目大意： n 个点，m 条双向边. 之后 m 行 每行三个整数 a，b，c 表示第 i 条边的起点，终点，权值. 要求每个点都走到且不超过两次. 求最小花费. 三.分析： 一道状压 DP 模板题 状压 DP 入门 详见代码. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include &l...

一.题目链接： HDU-3085 二.题目大意： 给你一个 n × m 的图，图由以下符号组成. '.' ：空地 'X' ：墙 'M' ：男 'G' ：女 'Z' ：鬼 规则： 男、女、鬼 都可以向上下左右四个方向走 每秒男的可以走三步，女的走一步，墙不能走. 每秒每个鬼 会分出子鬼占领距离他单位长度 ≤ 2 的方格（包括墙） 若男 || 女 被鬼抓住，则 GG. 问男、女是否能相遇，若能，则输出所需时间，若不能，则输出 -1. 三.分析： 这题就是双向 BFS  + 模拟. 详见代码吧. 四.代码实现： #include <se...

一.题目链接： HDU-3085 二.题目大意： 给你一个 n × m 的图，图由以下符号组成. '.' ：空地 'X' ：墙 'M' ：男 'G' ：女 'Z' ：鬼 规则： 男、女、鬼 都可以向上下左右四个方向走 每秒男的可以走三步，女的走一步，墙不能走. 每秒每个鬼 会分出子鬼占领距离他单位长度 ≤ 2 的方格（包括墙） 若男 || 女 被鬼抓住，则 GG. 问男、女是否能相遇，若能，则输出所需时间，若不能，则输出 -1. 三.分析： 这题就是双向 BFS  + 模拟. 详见代码吧. 四.代码实现： #include <se...

一.题目链接： HDU-3085 二.题目大意： 给你一个 n × m 的图，图由以下符号组成. '.' ：空地 'X' ：墙 'M' ：男 'G' ：女 'Z' ：鬼 规则： 男、女、鬼 都可以向上下左右四个方向走 每秒男的可以走三步，女的走一步，墙不能走. 每秒每个鬼 会分出子鬼占领距离他单位长度 ≤ 2 的方格（包括墙） 若男 || 女 被鬼抓住，则 GG. 问男、女是否能相遇，若能，则输出所需时间，若不能，则输出 -1. 三.分析： 这题就是双向 BFS  + 模拟. 详见代码吧. 四.代码实现： #include <se...

一.题目链接： HDU-1560 二.题目大意： 给你 n 个字符串 str. 让你求出一个字符串 s 的最小长度 使得这 n 个字符串都是 s 的子序列 三.分析： 一道 IDA* 的模板题.... 这里的评估函数就用 max(若s 包含 str[i]，还需的最小长度) 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include &...

一.题目链接： HDU-3533 二.题目大意： 第一行 4 个整数 m，n，k，d. m × n 是地图大小，有 k 个炮塔. d 是初始生命值，每秒消耗 1 点生命值. 之后 k 行. 每行有 ch，t，v，x，y. ch = {'N', 'S', 'W', 'E'} t 为该炮塔发射炮弹的间隔时间. v 为该炮台发射子弹的速度. x，y 为该炮台的坐标. A 的初始位置在 (0, 0)，出口在 (m, n). 若 A 生命值为 0 或 被子弹打中，则 A 死亡. ps：炮台可挡住其他子弹. 三.分析： 直接 BFS + 模拟... 详见代码. 四.代码...

一.题目链接： HDU-3533 二.题目大意： 第一行 4 个整数 m，n，k，d. m × n 是地图大小，有 k 个炮塔. d 是初始生命值，每秒消耗 1 点生命值. 之后 k 行. 每行有 ch，t，v，x，y. ch = {'N', 'S', 'W', 'E'} t 为该炮塔发射炮弹的间隔时间. v 为该炮台发射子弹的速度. x，y 为该炮台的坐标. A 的初始位置在 (0, 0)，出口在 (m, n). 若 A 生命值为 0 或 被子弹打中，则 A 死亡. ps：炮台可挡住其他子弹. 三.分析： 直接 BFS + 模拟... 详见代码. 四.代码...

一.题目链接： HDU-3533 二.题目大意： 第一行 4 个整数 m，n，k，d. m × n 是地图大小，有 k 个炮塔. d 是初始生命值，每秒消耗 1 点生命值. 之后 k 行. 每行有 ch，t，v，x，y. ch = {'N', 'S', 'W', 'E'} t 为该炮塔发射炮弹的间隔时间. v 为该炮台发射子弹的速度. x，y 为该炮台的坐标. A 的初始位置在 (0, 0)，出口在 (m, n). 若 A 生命值为 0 或 被子弹打中，则 A 死亡. ps：炮台可挡住其他子弹. 三.分析： 直接 BFS + 模拟... 详见代码. 四.代码...

一.题目链接： HDU-3567 二.题目大意： Eight 的升级版，游戏规则相同. 每次给出两个字符串 A, B，问 从 A 到 B 的最少步数 并 打印最小字典序的路径. 三.分析： 看了大神的分析才懂。。。 在这里阐述一下. 只考虑 X 的位置，由于 1 ~ 8 数字无特殊性 所以可将所给的 A 重新编号. 例如 A1：8 7 X 6 5 4 3  2 1 编号为 A2：1 2 X 3 4 5 6 7 8  并使用相同的编号规则 给字符串 B 重新编号 这样 A2 -> B2 就等价与 A1-> B1. 又因为 X 的位置只有 9 种情况，所以可...

一.题目链接： HDU-3567 二.题目大意： Eight 的升级版，游戏规则相同. 每次给出两个字符串 A, B，问 从 A 到 B 的最少步数 并 打印最小字典序的路径. 三.分析： 看了大神的分析才懂。。。 在这里阐述一下. 只考虑 X 的位置，由于 1 ~ 8 数字无特殊性 所以可将所给的 A 重新编号. 例如 A1：8 7 X 6 5 4 3  2 1 编号为 A2：1 2 X 3 4 5 6 7 8  并使用相同的编号规则 给字符串 B 重新编号 这样 A2 -> B2 就等价与 A1-> B1. 又因为 X 的位置只有 9 种情况，所以可...

一.题目链接： HDU-3567 二.题目大意： Eight 的升级版，游戏规则相同. 每次给出两个字符串 A, B，问 从 A 到 B 的最少步数 并 打印最小字典序的路径. 三.分析： 看了大神的分析才懂。。。 在这里阐述一下. 只考虑 X 的位置，由于 1 ~ 8 数字无特殊性 所以可将所给的 A 重新编号. 例如 A1：8 7 X 6 5 4 3  2 1 编号为 A2：1 2 X 3 4 5 6 7 8  并使用相同的编号规则 给字符串 B 重新编号 这样 A2 -> B2 就等价与 A1-> B1. 又因为 X 的位置只有 9 种情况，所以可...

一.题目链接： HDU-1043 二.题目大意： 八数码经典问题. 不懂的去玩 4399 三.分析： 挂上几个大佬的链接： 八数码解的存在性证明 康拓展开 直接 BFS TLE 了. 这里 反向 BFS 很妙，只搜索一次，把所有状态都记录下来. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <vector&gt...