rprp

动态规划

图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

全部文章 / 动态规划（共12篇）

CF1060F Shrinking Tree 题解来自专栏

考试题目的小数版本可以先考虑一个暴力，就是枚举一个点作为最后的点，然后枚举一个删边的序列。这个暴力显然比朴素的暴力复杂度要优秀一点。考虑基于这个思想来写题。可以枚举一个点作为最后的点，然后出所有的删边序列。算出在这个序列下点保留下来的概率，然后把所有的概率加起来，除以也就是左右序列的个数就是...

dp

2020-11-23

0 661

Luogu 3748 [六省联考2017]摧毁“树状图”

题目大意：求两条树上边不相交路径，使得删掉这两条路径上的点以后剩下的连通块数量最多。做法两条路径在树上大概会长成两个倒着的‘V’字形，考虑在某一个'V'的最上面那个点统计答案。于是统计答案的时候我们发现有几种统计法：父节点有一个'V'，子节点有一个'V‘。父节点...

2020-11-20

0 475

[CQOI2017]老C的键盘

发现题目给的很像一棵树。。。就把这棵树建出来。发现如果把大于小于号分别看成一条有向边，发现这个题目就是求这个图有多少个拓扑序。对于每一个拓扑序，直接$$12345$$这样标号就可以得到满足题目要求的序列。考虑树\(dp\), 设\(f(i, j)\)为\(i\)这个点在这个子树所形成...

dp

2020-10-15

0 492

题解 [AGC030F] Permutation and Minimum

我们把位置在\((2i - 1, 2i)\)的两个点叫做一对点。显然如果这对点两个都被限定了直接丢掉完事。如果有一个没有被限定就先留下来。注意到其他的形如\((-1, -1)\)的顺序是可以随便变化的，所以先不考虑，最后乘上一个阶乘就可以了。考虑用\(f(i, j, k)\)表示...

dp

2020-10-14

0 480

题解 AGC029E Pairing Points

考虑\(1\)号点向外连出一条边之后，整个圆被分成两个部分，每个部分肯定是内部连边然后一个点连一条边出来跨越一号点连出的那一条线。考虑对这种形状的部分进行\(dp\)。设\(f(i, j, k)\)表示\([i, j]\)这个区间内部匹配， \(k\)点向外连接的方案数， \(g(i,j,...

dp

2020-10-14

0 499

题解 [AGC028D] Chords

首先，按照boshi巨佬的说法，考虑每种联通块的出现次数。如果可以求出，答案就是每种联通块的出现次数和。再按照boshi巨佬的说法，一种定义联通块长相的方法是用编号最小的点和编号最大的点表示。于是设\(f[l][r]\)为\(l, r\)连通且外面的点不连接到里面的点，里面的所有边...

容斥 dp

2020-10-14

0 549

题解 P4233 【射命丸文的笔记】 && 考试T3

考虑每一条哈密顿回路在所有竞赛图中的出现次数。发现如果确定一个环，其他的边乱选就可以保证出现哈密顿回路。所以对于一条哈密顿回路，出现次数为\(2^{C_n^2-n}\), 减去的\(n\)为那\(n\)条边。哈密顿回路是\(1-n\)的一个排列首尾拼在一起，共有\(n!/n\)种。于是总...

计数多项式求逆

2020-08-14

0 503

[wqs二分模板] CF739E Gosha is hunting

题目链接首先一个很显然的想法就是直接\(DP\) 设\(f[i][j][k]\)表示抓前\(i\)个神奇宝贝用了\(j\)个宝贝球和\(k\)个超级球，有： \[f[i][j][k] = max (f[i - 1][j - 1][k] + p[i], f[i - 1][j][k - 1]...

期望ＤＰ wqs二分

2020-06-10

0 381

斜率优化DP刷题单

Luogu P3195 [HNOI2008]玩具装箱 Luogu P2900 [USACO08MAR]Land Acquisition G Luogu P5785 [SDOI2012]任务安排 Luogu P4360 [CEOI2004]锯木厂选址 Luogu P2120 [ZJOI2007]仓库建...

斜率优化

2020-06-07

0 360

CF149D Coloring Brackets

DP神题。。。设\(dp[i][j][0/1/2][0/1/2]\)表示\([i,j]\)这个区间内端点取不染色/染红色/染蓝色三个状态然后转移。一个新\(trick\)就是这里的转移只要考虑这个区间内的串是合法的就可以了 #include <cstdio> #include <...

区间DP

2020-05-15

0 417