Cruiying

dp

2-sat(1) BSGS(2) dfs(2) dp + 线段树(1) floyd(3) Hash(1) KM算法(1) Kruskal重构树(2) LCA(6) manachar(2) Mendix(4) tarjan(1) 中位数(1) 主席树(2) 二分(3) 分数规划(3) 前缀和优化dp(2) 单调栈(6) 单调队列(1) 单调队列优化dp(1) 博弈(2) 后缀数组(15) 字典树(1) 差分约束系统(1) 并查集(4) 异或(2) 思维(2) 思维题(4) 扩展欧几里得算法(1) 拉格朗日插值(2) 数论(8) 未归档(15) 构造(1) 枚举(1) 模拟(3) 模板(1) 水题(4) 矩阵加速(2) 线段树(3) 网络流(2) 莫比乌斯反演(2) 莫队(4) 蓝桥杯(1) 规律(2) 贪心(2) 输入输出(1) 题解(1)

/ 注册

全部文章 / dp （共63篇）

51nod 1042 数字0-9的数量(数位dp)

给出一段区间a-b，统计这个区间内0-9出现的次数。数位dp #include <bits/stdc++.h> #include <iostream> #include <string.h> #include <math.h> using name...

dp

2019-08-29

0 617

luogu P2657(数位dp)

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？数位dp #include <bits/stdc++.h> #include <iostream> #...

dp

2019-08-29

0 440

CF1036C(数位dp)

定义一个数字是“好数”，当且仅当它的十进制表示下有不超过3个数字1∼9 举个例子：4,200000,102034,200000,10203是“好数”，然而4231,102306,72774200004231,102306,7277420000不是给定[l,r]，问有多少个x使得l≤x≤r，且x是“...

dp

2019-08-29

0 470

atcoder S - Digit Sum(数位dp)

给你一个n和d，求1-n中有多少个数位和是d的倍数数位dp #include <bits/stdc++.h> #include <iostream> #include <string.h> #include <math.h> using names...

dp

2019-08-29

0 1394

CF204A(数位dp)

小象非常喜欢区间中的数. 此时他有一対整数l和r(l<=r). 小象需要找到满足以下条件的x(l<=x<=r),使得数x的第一个数字与最后一个数字相等. 例如, 101, 477474,9101,477474,9是符合这个条件的,而47, 253, 102047,253,1020则...

dp

2019-08-29

0 414

核心城市 (树形dp+二分 + 树直径中心)

X 国有 n 座城市，n−1 条长度为 1 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。 X 国国王决定将 k 座城市钦定为 X 国的核心城市，这 k 座城市需满足以下两个条件：这 k 座城市可以通过道路，在不经过其他城市的情况下两两相互到...

dp

2019-08-27

0 438

atcoder O - Matching(状态dp)

状态压缩裸题https://atcoder.jp/contests/dp/tasks/dp_o #include <bits/stdc++.h> #include <iostream> #include <string.h> #include <math.h...

dp

2019-08-23

0 1331

atcoder M - Candies(前缀和优化dp)

有n个位置，每个位置最多可以放a[i]个物品，现在你有m个物品想要全部放到位子上，求共有多少种放法？设dp[i][j] 为前i个位置放了j个物品的方案数然后我们可以想到枚举位置;然后在枚举前面一共放了多少个物品;在枚举当前位置放多少个物品代码：复杂度为O(n * m ^ 2) 很明显超时 for...

dp

2019-08-22

0 1022

atcode L - Deque (记忆化搜索）

给你一个长度为n个序列，有两个人 Taro 和 Jiro，这两个人每次可以从序列的头部和尾部取数求x - y #include <math.h> using namespace std; typedef long double lld; typedef long long ll; co...

dp

2019-08-22

0 736

atcode I - Coins(概率dp)

题意：给你N个硬币，每个硬币正面朝上的概率为p[i],反面朝上的概率为1 - p[i]求正面朝上硬币数量比反面朝上硬币的数量多的概率是多少设dp[i][j] 为前i个硬币有j个硬币朝上的概率和所以可得出转移方程为：dp[i][j + 1] += dp[i - 1][j] * p[i] //表示当...

dp

2019-08-22

0 417