hdu 4272 状态树解法
source link: https://blog.csdn.net/yanxiangtianji/article/details/7971087
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
比赛的时候我第一时间就认为贪心是不对的，于是就写了个dfs型的DP，配了个状态树，就当是练习DP了。
这两天看网上大家说贪心最近的那个也可以，但是我一直还没理解，求证明。
言归正传，本题一般DP的话状态(len,arr[0..p])异常的大，有1001个长度，1000个位置，每个位置可能存在1000个不同的值，都保存必然超内存。
另外考虑到每次的操作都是针对序列末端的少了元素进行的，序列前面大段的内容都没有变化，于是考虑使用状态树压缩存储。
由于题目要求只要存在一个解就可以返回了，所以每个状态需要记录的内容非常简单，就是从此下去搜索是否会失败（若到此状态可以成功则算法就直接退出了，不需要继续）。算法进行时若发现当前状态会导致失败，则直接返回上一个状态。
每个节点有一个布尔标志表示从根到此节点为止的序列是否一定会导致最终结果失败，对于还不确定的自然是标记为否啦；以及一个子节点列表。这里我为了省事，就用了STL的map（比赛的时候我为了验证每个元素是否都出现了偶数次，还做了编号重排，把内元素的编号变到0到999，如果做了这一步，在节点里面也可以开一个1000的数组）。
注意：我们发现某个时刻arr[0..k]对应的状态会失败并不意味着arr[0..j],0<=j<k对应的状态也会失败，这也就是为什么每个节点都有一个failed标记而不用是否存在某个节点作为判断依据的原因。
Recommend
-
45
系统设计的万能解法：SNAKE原则
-
42
“还记得八皇后的解法吗？” “上个世纪的事情，不记得了。” “…… 现在回忆一下？” “开会，回头说。” “ fuck u ” “ u shit ” 我有一个C++基友，这么称呼是因为他入行时用的是C
-
6
题意略。 思路： 这一发A得实在是难能可贵。因此我要记录一下。 首先这个题很明显是个数位dp，其难点在于如何知道填到当前这一位时，我的最长上升子序列是多长。 如果是一个简单的求最长上升子序列的题，...
-
6
HDU OJ一些题目 关于做题这回事，引用一下： Chao Xu，Haskell用户.acm算是用来训练秒面试题的一个方式。 像我这种非cs系学生全靠玩acm的训练秒各个公司。深以为...
-
5
Armin's BlogHDU1171 Big Event in HDU（01背包）March 09, 2016题目链接 题意：n 个设备，每个设备一行代表价值和数量，要求把所有...
-
7
Armin's BlogHDU 1232 畅通工程（并查集）November 30, 2015题目链接 中文题，最简单的并查集。午休时间怒 A 一发~ #inclu...
-
9
Armin's BlogHDU 5584 LCM Walk（数学）November 30, 2015题目链接
-
11
Armin's BlogHDU 4389 X mod f(x)（分段打表）November 22, 2015分段打表，适用于求一段和。 题目链接 题意： 判断[A, B] (...
-
5
HDU 4496 D-City（并查集）November 27, 2015题目链接 题意：第一行输入 N（0 < N <= 10000 ）和 M（0 < M <= 100000 ）分别代表节点数和边数，接下来 M 行...
-
7
Armin's BlogHDU 1051 Wooden Sticks（贪心）November 30, 2015题目链接 题意：第一行 T 组数据，每组数据的第一行 n 代表有 n 个棍...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK