LargeDumpling

我只负责打字,内容我也不知道从何而来。

2015.11.30~2015.12.5

UVa1625:一道较难的DP,难以在构造完状态后再统计答案时,可试图在构造答案的同事累加答案,即“分解指标函数”或“计算未来费用”。

UVa10003:一道水DP,O(N^3)各做,可用四边形不等式优化至O(N^2),但是我始终觉得这题不是O(Nlog2N)就行了嘛?(也没试过)。

UVa1626:一道需要注意特(题)殊(中)情(的)况(坑)的DP题目,题目中说“空序列也是正规序列”,则意味着题目中可能出现空序列Orz。

UVa12186:一道树型DP。

UVa1220:一道树的最大独立集,可用树型DP做,也可用DFS序加贪心。

UVa1218:一道树的最小支配集的变式题目,同样可用树型DP和DFS序加贪心做法,不过至今没把树型DP调对。

UVa10817:一道状压DP,调了半天发现是数组开小了。

UVa1252:一道状压DP,卡了我很久。

UVa1412:一道状压DP,挺难的,卡了我一天。为了避免状态转移时每次重复构造下一个状态而带来额外的时间损耗,可将状态先构造好存下来,构造好转移关系,从而避免重复的计算。为了方便输出答案,可为每个状态维护一个pre,记录这个状态在最优情况下是由哪个状态转移过来的。若需要,还可额外维护一个opt记录在最优情况下由上个状态转移过来时采取的决策。

UVa11582:一道斐波那契数列的扩展。

UVa12169:一道同余方程相关的题。

UVa10375:唯一分解定理。

UVa10791:唯一分解定理,需要打表找出答案的规律。

UVa12716:最大公约数,当有多组询问时应当想到预处理答案,然后问啥答啥。
共计:14道/6天,约2.3道/天

评论

© LargeDumpling | Powered by LOFTER