已注销

动态规划

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

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

HDU-4405-Aeroplane chess

ACM模版描述题解概率 DP ，求期望。状态转移方程很容易想，设 dp[i] 表示在位置 i 还需要多少期望才能到达终点，那么 dp[n]=0 ，求 dp[0] 即可。状态转移方程如下： dp[i]=∑x=16dp[i+x]6.0+1...

2021-05-21

0 381

51Nod-1635-第K个幸运排列

ACM模版描述题解 1∼n 的排列数是 n! ，阶乘的增长速度是恐怖的，题目中 1≤n,k≤109 ，那么 n 只要超过 13 ， 13!=6,227,020,800 ，已经超过了 k 的最大范围，所以我们很容易想到的是，将 1∼n ...

2021-05-21

0 369

51Nod-1054-最长等差数列

ACM模版描述题解额，最近不知道 51Nod 怎么了，一下子井喷了好多题，不过这个题就是 1055最长等差数列的一个数据弱化，直接贴 1055 的代码稍微改一下数组开的大小即可。代码 #include <cstdio> #include <alg...

2021-05-21

0 453

51Nod-1157-全是1的最大子矩阵

ACM模版描述题解很经典的一个问题，最大 1 矩阵模板，直接套。代码 #include <iostream> using namespace std; const int N = 105; int m, n; bool a[N][N]; int Run(...

2021-05-21

0 486

51Nod-1032-骨牌覆盖 V2

ACM模版描述题解数据弱化的一个题，原题是 51Nod1033骨牌覆盖V2 ，插头 DP 。代码 #include <iostream> #include <algorithm> #include <cstring> #include &...

2021-05-21

0 354

51Nod-1803-森林直径

ACM模版描述题解根据题目，我们知道，数据是随机建树的，所以树的深度不会特别大，约摸 lg n ，所以我们可以树归搞搞，亲测，数据随机建树深度最大不超过 61 ，大一点没毛病，小一点就 WA ，至于官方题解中所说的解法，不是特别会写，只给大家贴一下参考参考。官方题解： ...

2021-05-21

0 261

51Nod-1833-环

ACM模版描述题解图论的问题我没有怎么深入学习，多数都是交给了队友去搞，所以看到这个题时，只知道是图上状压 DP ，却不知道具体从何入手。看了题解发现，原来形成不相交的简单环其实就是二分图的完美匹配，最后要求的就是二分图的完美匹配的个数取模。所以我们定义 dp[i][j] ...

2021-05-21

0 366

HDU-6006-Engineer Assignment

ACM模版描述题解常规的状压 DP 套路。给定 N 个任务和 M 个工程师，每个任务都有不超过三个的领域人才需求，每个工程师都有不超过两个领域精通。问在工程师只能使用一次的情况下，最多完成多少任务？题目的数据很明显的告诉我们要用状压 DP ，设置...

2021-05-21

0 368

HDU-6004-Periodical Cicadas

ACM模版描述题解在 n∗m 的区域中，有 n∗m 种知了，给出每种知了第一次出现的年数 s 和周期性 z ，然后询问 (x1,y1) 和 (x2,y2) 为对角线顶点的矩形区域中，所有种类知了同时出现的年份。这里要求矩形区域中所有知了第一次...

2021-05-21

0 410

51Nod-1835-完全图

ACM模版描述题解最近懒了好多，写题少了好多，闲来无事水一发…… DP 问题，设 dp[i][j] 表示前 i 个点形成 j 个连通块的方案数，具体细节看官方题解吧，不难理解。懒得写 Latex 表达式了…… 代码 #include &l...

2021-05-21

0 422