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

NC15553

首先有暴力枚举左端点和右端点的做法，加上前缀和优化，时间复杂度为发现时间复杂度瓶颈在于枚举左右端点，考虑从这里着手优化。发现枚举左端点后右端点最优解确定，所以可以只枚举左端点，时间复杂度答案为。

dp

2020-03-27

0 472

LG5003 跳舞的线 - 乱拐弯线性DP

问题描述 LG5003 题解设 \(mx[i][j][0/1]\)代表当前位置、朝向的最大拐弯数，最小同理。来源为左边和上边。坑点：起点可能为#。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespac...

2019-10-03

0 416

LG3092 「USACO2013NOV」No Change 状压DP

问题描述 https://www.luogu.org/problem/P3092 题解观察到 \(k \le 16\) ，自然想到对 \(k\) 状压。设 \(opt[i]\) 代表使用硬币状况为 \(i\) 时，最多可以买到 \(opt[i]\) 个物品。然后 \(opt[i]...

2019-10-02

0 335

LG4158 「SCOI2009」粉刷匠线性DP

问题描述 LG4158 题解设\(opt[i][j][k]\)代表到\((i,k)\)刷了\(j\)次的方案数。一开始DP顺序有点问题，调了很长时间。务必考虑清楚DP顺序问题 \(\mathrm{Code}\) #include<bits/stdc++.h> ...

2019-10-02

0 359

LG2679 「NOIP2015」子串线性DP

问题描述 LG2679 题解设\(opt[i][j]\)代表A串前\(i\)个，匹配\(B\)串前\(j\)个，选择了\(k\)个子串的方案数。转移用前缀和优化一下。 \(\mathrm{Code}\) #include<bits/stdc++.h> using ...

2019-10-02

0 415

LG1879 「USACO2006NOV」Corn Fields 状压DP

问题描述 LG1879 题解设\(opt[i][j]\)代表前\(i\)行，且第\(i\)行状态为\(j\)的方案数。枚举\(j\)，再枚举\(k\)，\(k\)为上一行的状态。判断\(j,k\)能否共存（j&k==0）计数转移即可。必须加强位运算能力。 \...

2019-09-30

0 387

LG1131 「ZJOI2007」时态同步树形DP

问题描述 LG1131 题解正难则反，把从一个点出发到叶子结点看做从叶子结点走到那个点。 DP方程很显然。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; #define int lon...

2019-09-27

0 376

LG2145 「JSOI2007」祖码区间DP

问题描述 LG2145 题解把颜色相同的一段看做一个点。然后类似于合唱队区间DP即可。但是这题好像出过一些情况，导致我包括题解区所有人需要特判最后一个点。 \(\mathrm{Code}\) #include<bits/stdc++.h> using name...

2019-09-25

0 373

UVA1401 Remember the word DP+Trie

问题描述洛谷（有翻译）题解 DP，设\(opt_i\)代表前\(i\)个字符方案数。 Trie优化，刷表法。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; template <...

2019-09-25

0 397

LG5202 「USACO2019JAN」Redistricting 动态规划+堆/单调队列优化

问题描述 LG5202 题解 \[opt[i]=xx+(cnt[i]-cnt[yy]<=0)\] 发现\(cnt[i]-cnt[yy] <= 0\)只能有两种取值于是直接堆优化即可 \(\mathrm{Code}\) #include<bits/stdc++...

2019-09-22

0 429