djs

空間換時間

1

C++系统快排速度并不是最快的，本题随机化快排完秒之。
TTTTTTT RRRRRR U U TTTTTTT H H
T R R U U T H H
T R R U U T H H
T RRRRRR U U T HHHHHHH
T R R U U T H H
T R R U U T H H
T R R UUUUU T H H

刚开始用的“字符长度排序”及“二分查找区间”，再用一个“排序”，结果和暴力是一样的，过四组。（即程序中的注释部分）
后改用“字符数组字典序排序”，加上“二分准确查找”，最后一个一样的“排序”，果然很快，0.662秒lu过，无压力。
（以上所谓“排序”均为“手动随机化有附带值快排”）
（“二分查找区间”找到的是同一长度的字符数组的范围，“二分准确查找”找到的就是最终要找的那个字符数组）
（不过字典树优化后其实应该可以更快的，不过在NOIP中其实完全可以用其他的东西来代替字典树，所以，在NOIP以后再学学字典树吧，毕竟是很好用的一种数据结构）

只能用堆优化DJS，别的都超时SPFA超时两个点

数值递推，
（推公式当中就会发现发现，
递推式明显和“全排列”的公式有关。）

字典樹

唉,比赛的时候数组开小了.....错了1组
1.字符串排序
2.二分查找,累加
3.累加后数据排序
4.输出

小号用更快的堆无压力lu过。（但是下面显示的“最近提交程序”似乎是朴素算法……）

用堆的无压力lu过。

其实本质就是高精度加法，输入输出时稍作处理即可。

树形动规
总是默认节点1为根节点，
动规时从根开始，但先填儿子节点，再处理根节点本身。（于是|）
f[i][0]表示不选i节点时的最大获利。 |
f[i][1]表示选择i节点时的最大获利。 |
|
动规时用到了递归。 <--------------------------------------------+
最后输出f[1][0]和f[1][1]中较大的。

找题解，上http://paulinsider.at.ua/news/ctravel/2011-11-09-12，快，稳，准，大牛的选择！

树形DP，填根节点时先填其儿子节点，全题设一号节点为根节点。
f[i][1]表示拜访奶牛i所得到的最大拜访量。
f[i][0]表示不拜访奶牛i所得到的最大拜访量。
用了递归。
目标状态为：f[1][0]与f[1][1]中大的一个。

一定要看清题认真写

小号飘过……

普通手动快排：0.061
随机化手动快排：0.069
不解了，唉……
（本题其实就是两次排序，总的排序+相邻数的差的排序）

寬搜

找题解！！！上http://paulinsider.at.ua/news/protifz/2011-11-09-10，快，稳，准，大牛的选择！！