Rewinner

DP

ACM(1) dfsdd(1) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

全部文章 / DP （共6篇）

2019 西安邀请赛 J And And And【树形DP】

传送门思路：如果要求异或为0的路径的个数，这就是一个***题。但是他要求的集合的个数。可以从刚才那个问题扩展开来，问有多少条路径的子路径的异或值为0。这是一个计数的问题，我们知道异或有一个性质 x^x=0 1为树的根节点，xor[i] 表示i到根节点路径上的的异或值我们可以发现当两个点(s...

2019-07-17

0 573

南华大学第十五届ACM 神秘的字符串【区间DP】

传送门思路：很容易想到这是一道区间DP的题，但是如何写区间DP方程，二维好像表示不了，那三维呢？好像也不好想，那就四维。，表示区间中 u 字符连着消去 k 长度的最大价值( 只有两个字符，即 0和1 ) s 表示区间的一个点，如果那么dp 转移方程表示区间的最大价值细节见代码： ...

2019-04-21

0 565

数位DP 求满足条件的和

这是一个板子：求数位DP中满足一些条件的数的和方法：如果我们求满足条件的数的个数只需要开一个数组就行。如果我们求满足条件的数的和，则需要开一个数组结构体 node 里面有两个元素，一个是cnt，一个是sum。 cnt就是记录满足条件的数量，sum就是记录满足条件的数字和。...

2019-01-11

0 582

HDU1074：Doing Homework(状缩DP)

题意：有n门课，每门课有截止时间和完成所需的时间，如果超过规定时间完成，每超过一天就会扣1分，问怎样安排做作业的顺序才能使得所扣的分最小（相同答案输出字典序较小小的答案）思路：用二进制压缩状态，比如110，表示第二门和第三门课程完成，第一门课程没有完成。我们的dp[i]意思是在i这个状态下能够扣...

2019-01-09

0 610

Mondriaan's Dream POJ - 2411 状压（有注释）

状压的方法参考博客：https://blog.csdn.net/hopeztm/article/details/7841917?utm_source=tuicool&utm_medium=referral 大佬的博客思想很好但是时间复杂度很高。我利用大佬状压的思想写的DFS记忆化，跑了...

2019-01-07

0 476

B number 数位DP

题意很简单就是要你寻找数字含有13字串并且能够被13整除的数。我自己的写法和大佬的做法都不一样，时间也比他们的慢很多，跑了（200+ms）。大佬的博客：https://blog.csdn.net/libin56842/article/details/10026063 大佬的DP是三维，而...

2019-01-07

0 474