已注销

动态规划

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篇）

51Nod-1849-Clarke and package

ACM模版描述题解官方题解：代码 #include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int MAXN = 300...

2021-05-21

0 347

51Nod-1868-彩色树

ACM模版描述题解树型DP，先上官方题解：官方题解说的十分清楚，和我的代码思路也恰好吻合，大体上是针对每种颜色求出不包括该种颜色的路径的点对儿数目之和。最后用 col_num∗cal(n) 减去前边求的和即为树上任意不同两点之间路径包含的颜色种类之和，然后再乘以 (n−...

2021-05-21

0 538

HDU-6249-Alice’s Stamps

ACM模版描述题解 DP 问题，设 dp[i][j] 表示前 i 个位置选取 j 个区间的最优解。当然 i 要加以处理，因为我们需要 i 是某个区间的右端点，这样选取区间才完整，具体的处理方法也很容易理解，直接看代码吧~~~ 代...

2021-05-21

0 385

四边形不等式优化之石子归并与矩阵链乘之区别

ACM模版很久以前做过一个环形石子归并的题目，因为数据较大、复杂度较高， O(n3) O ( n 3 ) ，所以 TLE T L E 了，需要用到四边形不等式优化一下，几乎降低复杂度到 O(n2) O ( n 2 ) ，才能 AC A C 。我们先来看一下这个题目：描述：...

2021-05-21

0 556

CF-Avito Code Challenge 2018-E-Addition on Segments

ACM模版描述题解给定 n n 个值为 0 0 的数，下标从 1∼n 1 ∼ n ，然后给了 q q 次区域加操作，选取这 q q ...

2021-05-21

0 403

CF-Avito Code Challenge 2018-D-Bookshelves

ACM模版描述题解按位贪心， dp check d p c h e c k 。稍微详细点说，那就是按照二进制位从高位开始往低位贪心，贪心第 bit b i t 位时，检查是否可以达成分为 k k 堆，每堆和的第 bit ...

2021-05-21

0 397

CF-Codeforces Round #485 (Div. 2)-C-Three displays

ACM模版描述题解设 dp[i][j] d p [ i ] [ j ] 表示取第 j j 个数为第 i i 个值， i:1∼3，j:0∼n−1 i : 1 ∼ 3 ， j : 0 ∼ n − 1 ，最后输...

2021-05-21

0 350

牛客网-2018 美团 CodeM 编程大赛-资格赛-3-世界杯

ACM模版描述题解这个题可以用暴力，因为数据很小，也可以用 dp d p ，初始化 16 16 只队伍，一共需要比赛四轮，所以我们可以通过前一轮的胜率推后一轮的，这里需要注意的是，每轮比赛的两个人在此轮分组中分布在前半部分一个，后半部分一个。代码 #inclu...

2021-05-21

0 429