【洛谷 P4934】 礼物 (位运算+DP)

题目链接

位运算+\(DP\)=状压\(DP\)?(雾
\(a\&b>=min(a,b)\)在集合的意义上就是\(a\subseteq b\)
所以对每个数的子集向子集连一条边,然后答案就是这个\(DAG\)的最长链了,跑一遍拓扑排序就行了。

直接连边的复杂度是\(O(n^2)\),显然只能拿\(60'\)。
题解里的连边方法我没怎么懂然后因为穷又不能看直播讲解
但是我拿到\(70\)分暴力分后(不要问我为什么有70)看了别人的代码,发现一个很巧妙的方法,
无需建图,\(DP\)的思想,我写在洛谷博客里了

上一篇:洛谷P3373 [模板]线段树 2(区间增减.乘 区间求和)


下一篇:Java限流策略