蒟蒟独行

dp

01分数规划(1) AC自动机(2) bbp(1) cf(8) FFT(4) fleury(1) floyd(1) k-d树(1) kmp(1) kruskal重构树(1) lca(4) main(1) manacher(2) markdown(1) st表(1) trie(1) 一中(4) 主席树(1) 二分(2) 前缀和(1) 单调队列(1) 博弈论(3) 卡常(1) 双联通分量(5) 图论(1) 左偏树(1) 并查集(1) 强联通(2) 思维(11) 感想(6) 扫描线(1) 找规律(1) 技巧(1) 拓扑排序(2) 搜索(7) 数位dp(3) 数学(25) 斜率优化dp(1) 暴力(1) 最小树形图(1) 最短路(2) 未归档(1) 杂(15) 树(5) 树套树(2) 树形dp(4) 树状数组(5) 概率dp(1) 模拟(14) 模拟赛(2) 模板(30) 欧拉函数(1) 点分治(1) 状压dp(1) 生成树计数(1) 离散化(1) 算法复习(14) 线段树(20) 线段树合并(1) 网络流(2) 置换群(1) 虚树(1) 计算几何(1) 贪心(12) 轮廓线dp(1) 高斯消元(1) 高精度(2)

/ 注册

全部文章 / dp （共35篇）

洛谷P2679 子串

题目题解： f[j][k]表示：一定取到a[i]时，在B的前j位中取了k个子串的方法数 g[j][k]表示：a的前i位，B的前j位取了k个子串的方法数（对是否取到a[i]没有要求） f[i][j][k]+=f[i-1][j-1][k]（把这位接在原来的后面）+g[i-1][j-1][k-1...

2020-01-21

0 335

bzoj1019: [SHOI2008]汉诺塔

题目题解因为转移的优先顺序，所以到达每一个目标的转移过程是一定的。考虑dp方程： f[x][i]表示第x个柱子上有i个盘子，把他们都移动到g[x][i]这个柱子上要花得步数。首先考虑i=1，因为操作有优先顺序，因此g[x][1]可以确定，f[x][1]都是1。接下来考虑任意的i，那么我们需...

2020-01-21

0 490

bzoj1037: [ZJOI2008]生日聚会Party

题目题解用f[i][j][x][y]表示到第i个人，总共j个男生，以i结尾的任意长度中男生最多比女生多x，女生最多比男生多y的方案数。状态转移如下：如果x+1<=k，f[i+1,j+1,x+1,max(y-1,0)]+=f[i][j][x][y] 如果y+1<=k，f[i...

2020-01-21

0 413

bzoj1044: [HAOI2008]木棍分割

题目题解 f[i][j]=Σf[i−1][k]{k|sum[j]−sum[k]<=ans1} f [ i ] [ ...

2020-01-21

0 361

bzoj2298: [HAOI2011]problem a

题目题解求最多说真话的人数，答案即为n-ans 设dp[i]表示在前i名中最多有多少人说真话 dp[i] = max{dp[j-1]+sum[j][i]} 其中sum[j][i]表示名次区间为[j, i]的人数 #include<bits/stdc++.h> using n...

2020-01-21

0 423

51nod 1780 完美序列

题目题解先预处理出来每种大小的数的个数，并在这个过程进行判断是否连续（不大于 1），然后，我们可以从小到大进行插空法插数，那么如何插呢？假如，此时我们已经查到数 i，那么合法的插孔分为两种，第一种是插在两个 i−1 i ...

2020-01-21

0 327

51nod1048 整数分解为2的幂 V2

题目题解程序可以看我的，我的A了，当然，有些地方还可以优化，但我懒得优化了 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int M=1e9; char s[31]; int tmp...

2020-01-21

0 414

bzoj4762: 最小集合

题解1 题解2 其实差不多，随便选一篇看好了

2020-01-21

0 415

51nod 1406 与查询

<article> Description </article> 有n个整数。输出他之中和x相与之后结果为x的有多少个。x从0到1，000，000 Input 第一行输入一个整数n。(1<=n<...

2020-01-21

0 484

bzoj3997: [TJOI2015]组合数学

题目题解 Solution: 将每一个财宝抽象成一个点，这就变成了一个有向无环图的最小路径覆盖，对于这类问题，我们知道最长反链=最小路径覆盖，所以求出这张图的最长反链就可以了。对于一个点，它的左上角是可以到达的，但是右上角不能，所以用 ...

2020-01-21

0 358