expect2004

动态规划

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

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

LG5196 「USACO2019JAN」Cow Poetry 背包+乘法原理

\(\mathrm{Cow Poetry}\) 问题描述 LG5196 题解因为每句诗的长度一定是\(k\)，所以自然而然想到背包。设\(opt[i][j]\)代表到第\(i\)位时，结尾为\(j\)的方案数。背包，注意\(\mathrm{DP}\)顺序为先枚举\(i\)，后枚举单...

2019-09-22

0 587

LG2530 「SHOI2001」化工厂装箱员高维DP+记忆化搜索

问题描述 LG2530 题解设\(opt[i][a][b][c][d]\)代表装到第\(i\)个后，第\(1,2,3\)手上分别还剩\(a,b,c\)个的最小操作数。记忆化搜索即可。启示：如果状态没想法，可以先写爆搜，确定状态。 \(\mathrm{Code}\) #in...

2019-09-21

0 338

LG2893/POJ3666 「USACO2008FEB」Making the Grade 线性DP+决策集优化

问题描述 LG2893 POJ3666 题解对于\(A\)中的每一个元素，都将存在于\(B\)中。对\(A\)离散化。设\(opt_{i,j}\)代表\([1,i]\)，结尾为\(j\)的最小代价。 \[opt_{i,j}=min_{k \in [1,m]} {opt_{i-...

2019-09-21

0 372

TYVJ1071 LCIS 线性DP+决策集优化

问题描述 TYVJ1071 题解暴力\(\mathrm{DP}\) 首先，一个\(O(n^3)\)的解法：设\(opt_{i,j}\)代表\(a\)的前\(i\)个和\(b\)的前\(j\)个的\(\mathrm{LCIS}\). 显然有： 1.\(a_i=b_j\) \[o...

2019-09-21

0 540

LG3004 「USACO2010DEC」Treasure Chest 区间DP+滚动数组优化

问题描述 LG3004 题解把拿走的过程反向，看做添加的过程，于是很显然的区间DP模型。设\(opt_{i,j}\)代表区间\([i,j]\)中Bessie可以获得的最大值，显然有 \[opt_{l,r}=sum_{l,r}-min(opt_{l+1,r},opt_{l,r+1})...

2019-09-20

0 477

LG4516/LOJ2546 「JSOI2018」潜入行动树上背包

问题描述 LG4516 LOJ2546 题解好一个毒瘤题。 hkk：JSOI的签到题设\(opt[i][j][0/1][0/1]\)代表结点\(i\)的子树，放置\(j\)个，\(i\)放不放，\(i\)是否覆盖的方案数。 DP方程太长，无力打出（真·原因：我要睡觉！...

2019-09-18

0 388

LG2602/BZOJ1833 「ZJOI2010」数字计数数位DP

问题描述 LG2602 BZOJ1833 题解数位\(\mathrm{DP}\)板子题。注意限制位数、前导零。 \([a,b]=[1,b]-[1,a-1]\) \(\mathrm{Code}\) #include<bits/stdc++.h> using na...

2019-09-16

0 445

SP15637 Mr Youngs Picture Permutations 高维动态规划

问题描述 LG-SP 题解发现\(n,k\)都非常小，尤其是\(k,k\le 5\)，于是直接开\(5\)维进行\(\mathrm{DP}\) 用记忆化搜索实现。 \(\mathrm{Code}\) #include<bits/stdc++.h> using nam...

2019-09-15

0 394

动态规划专题选做

这是一个大坑，之后会慢慢整理上来的线性\(\mathrm{DP}\) 「TJOI2019」甲苯先生的字符串线性动态规划+矩阵加速 SP15637 Mr Youngs Picture Permutations 高维动态规划 LG5003 跳舞的线 - 乱拐弯「SCOI2009」粉刷匠 ...

2019-09-15

0 497