动态规划 - Page 6

POJ训练记录3
1379.RunAway模拟退火裸题[crayon-6942588b84160360973321/]2758.CheckingtheText暴力+哈希[crayon-6942588b8416f180058631/]poj3156.Interconnect由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化[crayon-6942588b841a1246612700/]1837.Balancef(i,j)前i个力矩为j的方案,dp[crayon-6942588b841b6287556522/]3609.ResetSequence状压+bfs初始集合是0-n-1每个指令会使得集合中的一些元素消失，目标状态是只有一个0[c...
02015年5月19日5,187递推与动规,广度搜索,状压动规,几何,哈希表,记忆化搜索,概率与期望

POJ训练记录2
3613.CowRelays求经过n条边的最短路，floyd+倍增QAQ[crayon-6942588b9ba89923789835/]2728.DesertKing最优比率生成树分数规划[crayon-6942588b9ba95229539041/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-6942588b9ba...
02015年5月17日7,498STL,贪心,prim,floyd,二分法,并查集,树形动规,2-SAT
2015全国互测 1
计算给定n,m对于[1,n]不包含m作为其子串的数k求\(\sum_ke^{k/n}\)kmp预处理后数位dp。。。[crayon-6942588b9c55d501496657/]移动小x有n张卡片和n个卡槽，现在第i张卡片在ai卡槽中。小x每次可以把一个在a位置的卡片移动到b位置，消耗的代价为min(|a−b|,n−|a−b|)，每张卡片可以被移动多次。小x想使得每个卡槽有且仅有一张卡片，请你告诉他最少需要的代价是多少。环形分金币参加白书[crayon-6942588b9c56e084480412/]分离小x喜欢分...
02015年5月17日3,967KMP,深度搜索,数位动规
CERC 2014 填坑计划(9 / 12)
又是一个深不见底的大坑9/12A.Parades树形dp，dp[x]=∑dp[son]可能还有从一个子树出发，到达另一个子树的路径在每个结点记录在这棵树最优解的情况下去掉覆盖的路径树根能到达的点，这个每次暴力合并每个结点用状压dp配对子树得出最优解[crayon-6942588b9cce4573624350/]C.Sum我傻逼了。。。枚举答案后二分（其实可以直接算）不合法的情况似乎是2的幂[crayon-6942588b9ccf3374887307/]D.Wheels模拟[crayon-6942588b9ccfa47079...
02015年5月16日5,539贪心,区间动规,STL,深度搜索,树形动规,二分法,状压动规
「CF507X」Codeforces Round #287 (Div. 2)
A.AmrandMusic排序贪心[crayon-6942588b9d5ea691250919/]B.AmrandPins算出距离除以直径[crayon-6942588b9d5f4677284313/]C.GuessYourWayOut!按位考虑[crayon-6942588b9d5f7294590859/]D.TheMathsLecture从后往前dpf(i,j,k)表示后i位，当前模为j，是否有后缀被K整除[crayon-6942588b9d5fb811074269/]E.BreakingGood广搜，选可用边最多的路径[crayon-6942588b9d602926373936/] ...
02015年5月16日3,321递推与动规,模拟,贪心,广度搜索
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-6942588b9dc4a190690753/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-6942588b9dc53283542982/]poj1635.Subwaytreesystems树的同构，哈希[crayon-6942588b9dc57683409938/]poj2419.Forests暴力即可[crayon-6942588b9dc5d903099057/]poj1717.Dominoesdp水题[crayon-6942588b9dc63890767328/]poj2949.WordRings建图+分数规划[crayon-6942588b9dc69618931927/] ...
02015年5月14日4,534递推与动规,spfa,深度搜索,二分法,并查集,哈希表
「CF540X」Codeforces Round #301 (Div. 2)
A.CombinationLock模拟[crayon-6942588b84a98522149513/]B.SchoolMarks塞一堆中位数，特判什么的[crayon-6942588b84aa1047251445/]C.IceCave深搜连通性，出点入度特判[crayon-6942588b84aa6689410944/]D.BadLuckIsland期望dp+记忆化[crayon-6942588b84ab3248419011/]E.InfiniteInversions离散树状数组乱搞[crayon-6942588b84ab8971025595/] ...
02015年5月13日3,827模拟,深度搜索,树状数组,记忆化搜索,概率与期望
PKUSC 2014 #1
A:unix纪元模拟[crayon-6942588b9e4c4999335151/]B:连环锁真心不会格雷码QAQ[crayon-6942588b9e4d4461438728/]C:Zhu'smultiset二分答案，得出每个数的增长开始时间[crayon-6942588b9e4dd630336554/]D:TeamThemUp!二分图染色+dp[crayon-6942588b9e4e1662760229/]F.Boatherds傻逼点分治[crayon-6942588b9e4eb903541714/] ...
42015年5月11日5,219递推与动规,模拟,STL,二分法,点分治,高精度,二分图染色
TLX Practice Contest
被练习赛虐QAQA快速冪脑补一下[crayon-6942588b9f112270756965/]B把两种行分开分别dp求前i行有j行两人都错然后枚举两种行分别两人都错了i，j用排列组合算一下贡献即可[crayon-6942588b9f11b605735507/]C二分+树形dp[crayon-6942588b9f125503077392/]...
62015年5月8日3,958递推与动规,二分法,树形动规,快速幂,排列组合
「CF543X」Codeforces Round #302 (Div. 1)
本场血崩A.WritingCode显然的n^3dp，滚动数组[crayon-6942588b9fd13293472484/]B.DestroyingRoadsn个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。\(1\leqn\leq500,1\leqm\leqn(n-1)/2\)题解其实就是问，至少需要多少条边，才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。如果这两条路径不相交，那么答案为dis(s1,t1)+dis(s2,t2)。如果相交部分为(p1,p2)，答案为p1,p2的...
12015年5月8日3,352递推与动规,树形动规,广度搜索
「BZOJ4011」[HNOI2015] 落忆枫音
Description「恒逸，你相信灵魂的存在吗？」郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫，枫茜突然问出这样一个问题。「相信吧。不然我们是什么，一团肉吗？要不是有灵魂……我们也不可能再见到你姐姐吧。」恒逸给出了一个略微无厘头的回答。枫茜听后笑了笑。「那你仔细观察过枫叶吗？」说罢，枫茜伸手，接住了一片飘落的枫叶。「其实每一片枫叶都是有灵魂的。你看，枫叶上不是有这么多脉络吗？我听说，枫叶上有一些...
02015年5月7日8,354递推与动规,拓扑排序
「JoyOI」五月有奖赛暨Loi 55 Round #1 Day2
抱枕被抢走了QAQ为何ZJ神犇要来虐蒟蒻控油刚捡肥皂[crayon-6942588ba0bb0051584538/]dC和俄罗斯方块我yy了一个奇怪的dp，高精模板太傻了就写了python[crayon-6942588ba0bbd107687737/]Loi_M的YoGiOh计划（byLoi_imcy）[crayon-6942588ba0bc3323787766/] ...
02015年5月1日3,667模拟,递推与动规,状压动规