标签 状压dp 下的文章:

BZOJ 2669: [cqoi2012]局部极小值 状压dp+容斥原理
发表于: | 分类:Oi | 评论:0 | 阅读:72
这题666 看到什么最小最大八成就是枚举最小值枚举最大值,这题显然是从小到大填,然后注意到最多有8个最小值所以显然是可以$f(i,sta)$状压dp的 如果写到这你就结束了然后过了样例然后get Wa…… 考虑你这么做只让X是局部最小值然后没让.不是局部最小值所以...

阅读全文>>

4774: 修路 斯坦纳树
发表于: | 分类:Oi | 评论:0 | 阅读:80
$f(i,sta)$ 表示第 $i$ 个点在联通块内并且这个点联通了 $sta$ 状态内的点 然后无脑跑斯坦纳树就行辣 注意跑出来之后还要把所有的合法状态放在一起取 $Min$, 因为显然根不同花费不一定相同 注意取的状态的合法性,在代码中体现为 $check$ ...

阅读全文>>

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

阅读全文>>

3717: [PA2014]Pakowanie
发表于: | 分类:Oi | 评论:0 | 阅读:61
神奇的状压$dp$ 开始的时候没想是状压……看24感觉非常的虚【忘了看90s的时限了 后来$Infinity37$教了我一发 首先我们把包按照容量从大到小排个序,因为显然如果$x$个小包能装的下$x$的大包当然也能装的下,所以先用大包 然后我们把物品的状态压压压,...

阅读全文>>

BZOJ 1097 [POI2007]旅游景点$atr$
发表于: | 分类:Oi | 评论:0 | 阅读:92
给出一张n个点m条边的无向连通图,现在一个人从1号点出发,想要遍历2~k+1号节点(不一定要按照顺序)然后到n号节点去,但是D个旅行顺序的要求,顺序要求的格式为D1,D2,代表在到达D2之前必须到达D1.问最短的旅行距离。 k太小了,一下子就有想法 直接全排列好像...

阅读全文>>

Title - Artist
0:00

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

TOP