动态规划 - Page 9

「BZOJ3036」绿豆蛙的归宿
Description随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为1/K。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？Input第一行:两个整数NM，代表图中有N个点、M条边第...
22015年2月27日5,391递推与动规,概率与期望

「BZOJ1369」[Baltic2003] Gem
Description给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。Input先给出一个数字N,代表树上有N个点,N<=10000下面N-1行,代表两个点相连Output最小的总权值SampleInput107512178941975610293SampleOutput14题解WJMZBMR：这题首先是不能用奇偶层染色的办法来做的，我构造出了至少需要1-3的反例，同时...
02015年2月27日3,192树形动规
「codechef」February Lunchtime 2015
懒得开多篇了LuckyFour 这题在逗我么[crayon-676fe40c16ec7253264791/]TheWarehouse发现实际上把一个东西移动到一个位置相当于不断做代价为1的交换所以只要枚举给3种字母赋权，求逆序对最小值即可[crayon-676fe40c16ecf612551899/]Heavy-lightDecompositions设f[i][j]表示i为根的子树，后代到i经过轻边数量不超过j树形dp，要用到前缀后缀积/逆元。。。[crayon-676fe40c16ed6235450901/] TheFirstCube 一眼分...
02015年2月23日3,695模拟,树形动规,素数测试,最大公约数与最小公倍数
「BZOJ2815」[ZJOI2012] 灾难
小强和阿米巴0.0fhq神犇的题==http://fanhq666.blog.163.com/blog/static/8194342620124274154996/[crayon-676fe40c17382064081388/]
22015年2月5日6,989树形动规,拓扑排序,最近公共祖先
「fjWC2015」三视图
「题目描述」史蒂夫想在minecraft里盖一座房子，众所周知，minecraft世界主要是由各式各样的立方体组成的。可惜的是，现在史蒂夫只拿到了建筑图纸的左视图和正视图（如下所示）。请问可能有多少种建筑符合给定的左视图和正视图，答案对10^9+9取模。方块不能悬空摆放。「输入格式」第一行一个整数n，表示正视图的列数。第二行n个整数，表示每列能看到的最高的立方体柱的高度。第三行一个整数m，表示左视图的列数。第四行m个整数，表...
12015年2月4日4,610状压动规
「fjWC2015」圣诞树
「题目描述」用m种颜色的彩球装点n层的圣诞树。圣诞树的第i层恰由l[i]个彩球串成一行，且同一层内的相邻彩球颜色不同，同时相邻两层所使用彩球的颜色集合不同。求有多少种装点方案，答案对p取模。只要任一位置上的彩球颜色不同，就算作不同的方案。「输入格式」第一行三个整数n,m,p，表示圣诞树的层数、彩球的颜色数和取模的数。接下来一行包含n个整数，表示l[i]。「输出格式」一个整数表示答案。「样例输入」321000312「样例输出」...
02015年2月4日3,728递推与动规,排列组合
「CF398B」Painting The Wall
Useraintadecidedtopaintawall.Thewallconsistsofn2tiles,thatarearrangedinann × ntable.Sometilesarepainted,andtheothersarenot.Ashewantstopaintitbeautifully,hewillfollowtherulesbelow.Firstlyuseraintalooksatthewall.Ifthereisatleastonepaintedcelloneachrowandatleastonepaintedcelloneachcolumn,hestopscoloring.Otherwise,hegoestostep2.Useraintachooseanytileonthewallwithuniformprobability.Ifthetil...
02015年2月1日4,072递推与动规,概率与期望
「CF83E」Two Subsequences
OnanITlessonValerastudieddatacompression.Theteachertoldaboutanewmethod,whichweshallnowdescribetoyou.Let{a1, a2, ..., an}bethegivensequenceoflinesneededtobecompressed.Hereandbelowweshallassumethatalllinesareofthesamelengthandconsistonlyofthedigits0and1.Let'sdefinethecompressionfunction:f(emptysequence) = emptystringf(s) = s.f(s1, s2) = thesmallestinlengthstring,whichhasoneofthepre...
292015年2月1日4,888递推与动规
「BZOJ2004」[HNOI2010] Bus 公交线路
Description小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路：1．设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。2．每个车站必须被一辆且仅一辆公交车经过（始发站和终点站也算被经过）。3．公交车只能从编号较小的站台驶往编号较大的站台。4．一辆公交车经过...
02015年1月31日4,710状压动规
「BZOJ3173」[TJOI2013] 最长上升子序列
Description给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？Input第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）OutputN行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。SampleInput3002Samp...
62015年1月29日8,145递推与动规,treap
「BZOJ3162」独钓寒江雪
Description题解参照2007杨弋论文vfk的博客http://vfleaking.blog.163.com/blog/static/17480763420134452440444/太神了orzorzorz[crayon-676fe40c1a9dc205485749/]
72015年1月28日4,812树形动规,哈希表
「BZOJ2073」[POI2004] PRZ
Description一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥.桥已经很旧了,所以它不能承受太重的东西.任何时候队伍在桥上的人都不能超过一定的限制.所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.Input第一行两个数:w–桥能承受的最大重量(...
02015年1月22日4,139状压动规