Fizzmy

区间DP

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

归档

标签

去牛客网

/ 注册

全部文章 / 区间DP （共3篇）

HDU5693 D Game-区间dp

vjudge传送门题意：有一个公差集合{D}，有n个数字每次执行以下操作： 1. 在当前剩下的有序数组中选择x(x≥2)个连续数字； 2. 检查1选择的x个数字是否构成等差数列，且公差 d∈{D} ; 3. 如果2满足，可以在数组中删除这x个数字； 4. 重复 1−3 步，直到无...

2021-08-18

0 361

BZOJ 2448: 挖油-区间DP+单调队列

题意： [0,x]中全是1，判断[1,n]中的点i中是0还是1需要权值 ai a i ，最坏情况下求得到x的最小权值 n<=2000 n <= 2000 Solution: f[i][j] f [ i ] [ j ] 表示只考虑[i,j]，最坏情况下求得到x的最小权值...

2021-08-18

0 282

BZOJ4565: [Haoi2016]字符合并-区间DP+状压DP

传送门题意：有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 1≤n≤300,0≤ci≤1,1≤wi≤109,k≤8 1 ≤ n ≤ 300 , 0 ≤ c i ≤...

2021-08-18

0 260