标签 dp 下的文章:

4886: [Lydsy2017年5月月赛]叠塔游戏 dp
发表于: | 分类:Oi | 评论:0 | 阅读:69
首先他要求要用上所有的牌【划重点】 看错题的可以回去重新想去了 然后我们考虑他那个递增P用没有,其实就是让你确定一组互不相同的底,然后让高的和最大 考虑在边权直接连边 然后考虑$i\to j$表示以$i$为底$j$为高 然后这题大概就变得傻逼了一半,显然就是每个点...

阅读全文>>

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

阅读全文>>

3456: 城市规划 CDQ分治+NTT 计数问题
发表于: | 分类:Oi | 评论:0 | 阅读:96
求$n$个点无向连通图的方案数 首先我们非常容易得到一个$n^2$的递推式,设$f(i)$表示$i$个点无向连通图的方案数,那么我们用所有情况的方案数减去不合法的方案数,不合法的话我们可以枚举$1$所在的联通块的大小进行计算,用$t(x)$表示$x$个点形成的完全...

阅读全文>>

4707: B君的技巧 DP
发表于: | 分类:Oi | 评论:0 | 阅读:67
非常神奇的一个dp 首先我们完全不要考虑在这个矩阵上划范围dp,这个思路会陷入瓶颈然后无法解决 把矩阵作为正常的权值矩阵然后考虑直接在值域区间上大力dp 注意到一个非常奇怪的约定是他们二进制上的第$k$位必须是完全相同的,然后由于这个更大的块也会满足这个所以其实是...

阅读全文>>

4903: [Ctsc2017]吉夫特 枚举子集 DP Lucas
发表于: | 分类:Oi | 评论:0 | 阅读:64
考试的时候结论都想到了然后分治FWT也想到了最后没想到小范围暴力GG 交BZOJ被卡常应该就我一个了吧…… 然后把分治FWT那个傻*算法扔到垃圾桶…… 注意到$\mod 2$ 意义下 $C_n^m = 1$ 当且仅当 n&m==n 证明的话你可以这样,你用...

阅读全文>>

Title - Artist
0:00

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

TOP