ymzqwq

DP

233(7) BZOJ(4) Codeforces(5) dfs(1) hdu(1) TopCoder(20) 不知道怎么分类(2) 乱搞(2) 分块(1) 博弈论(1) 图论(5) 平衡树(2) 并查集(4) 搜索(4) 数论(18) 未归档(3) 杂记(2) 树(4) 树状数组(1) 模拟/暴力(5) 游记(1) 笔记整理(3) 线段树(1) 贪心(5) 递归(1) 递推(1)

/ 注册

全部文章 / DP （共24篇）

TopCoder SRM 581 Div1 500 TreeUnion

一个环肯定是由两棵树中的边与中间连接的两条边组成的那么我们就可以用 c[0/1][k] c [ 0 / ...

2018-09-13

0 473

TopCoder SRM 589 Div2 1000 FlippingBitsDiv2

感觉讲不清。。 2018/9/28 UPD: 可以单个翻也可以整段翻然后就先靠单个翻把一段翻成一样的大概就是从左往右翻一波再从右往左翻一波再整个翻翻看? 我在讲什么 #include <bits/stdc++.h> using namespace std; const int N...

2018-09-12

0 594

TopCoder SRM 639 DIv2 1000 BoardFoldingDiv2

可以发现行和列其实没什么关系，于是我们愉快地分开处理，最后相乘。比如说现在在处理纵向的折痕：我们先把每列压成一个数，存入数组 a a ，这样就可以O(1)比较两列是否相等。然后我们再预处理出 f[i] ...

2018-09-07

0 537

TopCoder SRM 580 Div2 1000 WallGameDiv2

可以发现，Eel完全可以把路堵得很死，使得Rabbit只有一条路可走。并且Rabbit很聪明不会没事找抽往回走的。于是问题就转化为,从左上走到最后一行路过格子的权值和最大是多少。可以很容易地用DP解决， f[i][j][k] f ...

2018-09-02

0 362

TopCoder SRM 573 Div2 1000 WolfPackDivTwo

这题被边界问题坑了，我以为不会出事的，结果出了大事，cout，printf，还有不输出的答案全是不一样的，这波操作看得我一脸懵逼。。这题还挺简单的。用 f[i][j][k] f [ i ...

2018-08-28

0 441

TopCoder SRM 570 Div1 550 CentaurCompany

和Div2的1000类型差不多，都是个很套路的树形DP 我的做法暴力得要死，天晓得怎么过的。。 f[0/1][i][j][k][l] f [ 0 ...

2018-08-14

0 557

TopCoder SRM 570 Div2 1000 CentaurCompanyDiv2

这次的1000算简单的，就是统计有几个子树。树形DP一波， f[i] f [ i ] 表示以 i ...

2018-08-14

0 395

TopCoder SRM 682 Div2 1000 FriendlyRobot

大概思路是用 f [ i ] [ ...

2018-08-07

0 370

[hdu 4109] Instrction Arrangement

传送门就是个关键路径嘛，我一开始dfs还写挂了，于是上网找题解，怎么清一色topsort？？这还叫我怎么贺压根就不用啊，记忆化搜索具有天然拓扑序。怎么感觉网上好多题解都是贺来贺去的再次被hdu的多组数据坑了一发 #include<bits/stdc++.h> #defi...

2018-08-03

0 351

[POJ 2411] Mondriaan's Dream (轮廓线DP)

传送门轮廓线DP基础题。不得不说轮廓线DP的思想真的很精妙，但是轮廓线状态的表示方法我也是看了好久才理解。轮廓线的状态不是按照一般状压DP不太一样，个人觉得这篇博客讲得比较简短清楚，这篇博客虽然具体但是不太清晰，再结合一下代码应该就能理解了。话说我之前学的时候明明看到一篇很好的博客啊...

2018-07-28

0 390