标签 dp 下的文章:

4773: 负环 倍增Floyd dp
发表于: | 分类:Oi | 评论:0 | 阅读:170
我们先来讲一个比较厉害的做法 我们可以倍增Floyd,然后考虑答案必然等于一个数字 $x$ ,那么我们把他写成一个二进制,从高位到低位枚举当前是否合法,最后步数+1就是合法答案,类似倍增lca的求法 当然我这么懒……所以无脑暴力 $dp$ 一下吧…… $f(i,j...

阅读全文>>

ZJOI Day1 T1 仙人掌 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:149
考试的时候全程刚这题现在一看实在是有点亏啊………… 这题的仙人掌要求是没有重边的,那么我们可以在连完一种方案之后把剩下的没有被覆盖的边变成一个重边让他有覆盖 这样就变成了给定一棵树,找个方案使他的所有的边都被覆盖 树形dp即可 $f(x)$ 表示做完了 $x$ 的...

阅读全文>>

SRM 554 构造+dp
发表于: | 分类:Oi | 评论:0 | 阅读:179
T1 签到题,不会的看队爷题解吧 T2 这个T2非常妙啊,非常非常的好玩 给定一个序列,现在告诉你一个序列的价值为$\sum\limits_{i=1}^{len-1}{max{a_i,a_{i+1}}}$ 让你给出一个字典序最小的排列方案使得这个价值尽可能的小 考...

阅读全文>>

3899: 仙人掌树的同构 dp
发表于: | 分类:Oi | 评论:0 | 阅读:172
说好的字符串专题在我这直接变成dp了 23333333 这题求同构的仙人掌的方案数,我写了个 $n^2\log{n}$ 的做法【其实就是暴力 先随便找个点做跟,然后递归算儿子,$calc(x)$ 是计算 $x$ 子树的同构方案数。 如果 $x$ 是个链,有 $j$...

阅读全文>>

SRM 553 dp 差分约束
发表于: | 分类:Oi | 评论:0 | 阅读:153
250 pts 逗比题,给定一个全是0的无穷大的栈还有一个序列,每次取出序列的第一个元素,如果 $>0$ 就推到栈顶,如果 $=0$ 就把栈顶和栈顶下面的第一个元素弹出,求和,再把和推入,现在告诉你有一个元素不知道是啥以及最后的栈顶是多少,请求出该元素的值 ...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP