expect2004
expect2004
全部文章
动态规划 - ...
Codeforces Round(2)
Contests(11)
review(2)
其他(1)
动态规划(19)
动态规划 - 期望与概率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)
归档
标签
去牛客网
登录
/
注册
萌新expect的博客
由零至灵,由壹达意
全部文章
/ 动态规划 - 区间DP
(共3篇)
【题解】NC13230 区间DP
设 代表字符串 中 至 个字符,字符串 中 至 个字符是否能构成回文串。 然后区间DP套路转移。 时间复杂度 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int max...
dp
2020-03-25
0
773
LG3205/BZOJ1996 「HNOI2010」合唱队 区间DP
区间DP 区间DP: 显然是一个区间向左右拓展形成的下一个区间,具有包含关系,所以可以使用区间DP。 状态设计: 考虑和关路灯一样设计状态 因为不知道当前这个区间是从哪个区间拓展而来,即不知道这个区间最后一个进来的人站在了哪里 设\(f(i,j,0/1)\)代表区间\([i,j]...
2019-08-06
0
466
LG4170/BZOJ1260 「CQOI2007」涂***间DP
区间DP 发现可以转化为区间包含转移。 考虑区间\([l,r]\),分为两种情况。 \(col[l]=col[r]\) 此时相当于在涂\([l,r-1]\)或\([l+1,r]\)顺带着涂掉 \[f(i,j)=min[f(i+1,j),f(i,j-1)]\] 通常转移 枚举转...
2019-08-06
0
472