Fizzmy

DP

--------DP--------(1) CDQ分治(1) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(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 （共11篇）

Codeforces587B-DP+优化

Codeforces587B-Duff in Beach 传送门题意：给出一个有l个数的序列，序列每n个数一循环，在每个循环里取一个数，一共取1-k个数，要求取出来的子序列要递增，求方案数。n×k≤1e6 l≤1e18 Solution： DP，f[i][j]表示取了i次，最后一项取的...

2021-08-18

0 357

AtCoder Code festival 2017qualC-D-dp+优化

传送门题意：给你一个字符串s，问s最少分成几块，使得每一块在经过组合后都能成为一个回文串。（|s|≤2e5） Solution：我们可以转化一下“回文串”这个定义，对于每个字母我们可以把它分别转化到二进制的0-25位，然后如果一段字符串是回文串，那么这段字符串每个字符的异或一定是0或者...

2021-08-18

0 375

Codeforces 313D- Ilya and Roads

传送门题意：给一个区间[1,n]，再给出m个区间 [li,ri] [ l i , r i ] 以及每个区间的维修成本 vi v i ，问修好k个不同的整点所需的最小成本。（n≤300，m≤1e5） Solution：这道题首先想到了朴素的 n2m n 2 m 的dp（按照右端...

2021-08-18

0 298

BZOJ3039-玉蟾宫

权限题。题意：给一个n × m的01矩阵，求一个最大的全1矩阵，输出答案 × 3。（n,m≤1000） Solution：非常经典的一个模型，有两种方法，一种是贪心一种是dp，这里介绍一种dp方法——悬线法（安利王知昆dalao论文《浅谈用极大化思想解决最大子矩形问题》）悬线法的本质是...

2021-08-18

0 312

Codeforces 939F.Cutlet-单调队列优化dp

传送门题意：有2∗n的时间去煎一块两面的肉,给你k个可以翻转的区间 [li,ri] [ l i , r i ] ,可以在区间内翻转任意次, 保证区间不相交问是否存在合法的方案使得两面恰好都只煎了 n 分钟,并求最小翻转次数 n<=100000,k<=100 Soluti...

2021-08-18

0 658

洛谷P1846 游戏-DP

传送门题意：给定两个正整数数列，你要用它们来做一个游戏：你需要对数列进行若干次操作，每一次操作，应选择两个正整数 k1 k 1 和 k2 k 2 ，并删除第一个数列的最后 k1 k 1 个数，计算出它们的和 s1 s 1 ；删除第二个数列的最后 k2 k 2 个数，计算出它们的和...

2021-08-18

0 283

Codeforces1295F Good Contest-DP

题目大意：传送门长度为 n n n 的数列，第 i i i 个数可能的值为 [ l i , r i ] [l_i,r_i] [li,ri]，求数列为不严格单调递减数列的期望。（ 2 ≤ n ≤ 50 , 0 ≤ l i ≤ r i ≤ 1 e 9 ）（2\leq n \leq 5...

2021-08-18

0 288

牛客第7场I-Valuable Forests prufer序列+DP

传送门题意：定义一个无根树的权值为所有点的度数的平方和，求有标号的n个点形成的所有森林的权值的和。 T ≤ 5000 , N ≤ 5000 T\leq 5000,N \leq 5000 T≤5000,N≤5000 Solution: 比赛时脑抽，考完五分钟后过了… 由prufer序...

2021-08-18

0 410

Codeforces 1485E Move and Swap-DP

Codeforces 1485E Move and Swap-DP 传送门题意：一棵n个节点的树，叶子节点的深度都相同，每个节点有一个权值 a i a_i ai，有红蓝两个棋子，初始在根节点1，每轮进行三步操作： 1.红棋子移动到当前所在节点的儿子上 2.蓝棋子移动到当前节点层数+1...

2021-08-18

0 295

Codeforces 1485F-Copy or Prefix Sum-DP

Codeforces 1485F-Copy or Prefix Sum-DP 传送门题意给你一个n个数的序列 b b b 求有多少个序列 a a a满足对于每个 i ( 1 ≤ i ≤ n ) i(1\leq i\leq n) i(1≤i≤n)，至少满足以下两个条件之一： 1. b i...

2021-08-18

0 325