iiiiikun
iiiiikun
全部文章
dp
bfs(11)
codeforce(2)
codeforces(49)
dfs(27)
icpc(2)
kmp(2)
kruskal(1)
min25(1)
spfa(3)
stl(3)
三分(1)
二分(11)
二分图(3)
二叉树(2)
二叉树遍历(1)
倍增(1)
几何(1)
前缀和(6)
剪枝(1)
动态规划(2)
单调栈(1)
博弈论(1)
双指针算法(1)
双端队列(1)
唯一分解定理(1)
回文(1)
图论(4)
堆(1)
字符串(2)
尺取法(1)
差分(4)
差分约束(1)
并查集(7)
循环节(1)
快速幂(3)
思维(5)
思维题(6)
拓扑排序(2)
排序(1)
数位dp(3)
数位交换(1)
数学题(1)
数据结构(7)
数论(17)
最大子矩阵(2)
最小生成树(8)
最短路(17)
最长公共上升子序列(1)
有向图强联通分量(4)
未归档(8)
权值线段树(2)
构造(2)
枚举(2)
栈(1)
树形dp(4)
树状数组(3)
树的直径(1)
概率(1)
模拟(1)
模拟赛(1)
模拟退火(1)
模板(9)
欧几里得(1)
欧拉回路欧拉路径(1)
牛客多校(1)
状态压缩(1)
矩形面积(1)
矩阵乘法(1)
矩阵快速幂(1)
离散化(1)
筛素数(1)
线段树(4)
网络流(3)
背包(1)
菜鸟(14)
蓝桥(23)
蓝桥杯(2)
蓝桥训练(2)
贪心(11)
递归(1)
递推(2)
链表(2)
队列(3)
题解(2)
马拉车(2)
高精度(1)
归档
标签
去牛客网
登录
/
注册
iiiiikun的博客
老废物了
全部文章
/ dp
(共65篇)
[HDU-6831]
分手了不太开心QAQ,写篇博客吧。这题是区间dp的问题,题意就是给你无限个1145141919,有t次询问,询问的n小于等于5000,问是否存在这样的前缀使得你操作无限次加、乘和括号,没啥思路,看了大佬的代码,发现是有规律的?我这种菜鸡来打表都不会,那当且仅当前缀长度小于等于13,那就区间dp好了,...
2020-12-17
0
469
概率dp 神仙题
题目大致意思: 总共有n种邮票,每选一张邮票,邮票的价格会加一,邮票的初始值是1,最后问拿完n种邮票的期望价格。 思路: 发表一下看这个题题解的感想:这个题太仙了,概率dp的套路司空见惯就是把数组定义成已经考虑前i个—到n的期望。那么我们先开一个数组来记录,f[]记录从已经选了i个从第i种开始选到第...
2020-12-17
0
372
Maze 概率dp
题意:有一棵树,主人公要从1开始走,逃生,问逃生的期望步数,在1这个点 不可能死也不可能逃生,在别的点有ei的概率逃生,ki的概率死亡并且回到1这个点。 思路: 真的是难推啊,我们定义f数组为在i这个点逃生的期望步数,由于是无向图,我们先从叶子结点考虑, f[i]=0e[i]+ k[i]f[1] +...
2020-12-17
0
423
F - Computer
题意:给定一棵树,求出每个点到树上所有点的最大距离。 思路: 先dfs预处理出来 考虑u这颗子树,往下走的最大值和次大值,然后每个点的最大值,来源一下面的最大值和它根节点往上走的最大值再取max,那么往上走的情况有两种例如下图: p代表u的父节点,根节点往上走的途径有两条,一条是继续往他的父节点走...
2020-12-17
0
0
I - Tree with Maximum Cost
题意:选择一个点作为根节点,然后每个顶点到它的花费为距离那个顶点的值。求最大值。 思路:也是树形dp,dp[i]代表考虑以i为根节点,他的子树对他的花费,sum[i]代表i整颗子树的节点个数和,那么dfs两次就行了,第一次dfs预处理出来sum和dp数组,第二次处理出每个点的答案。u节点的答案就是a...
2020-12-17
0
0
B - Zero Tree
题意:每次可以将包含1的节点的子树加1或者减1,问最小的操作数让整棵树变成0; 解题思路: 由于每次操作都要带上1,那么我们把1当做根节点,然后我们发现他的操作数与子树有关,先不考虑u这个节点,仅考虑他的子树,那么操作数有上升的也有下降的,那就是启发我们开两个数组,up,down记录上升的次数和下降...
2020-12-17
0
417
A - Distance in Tree
题意:给你一棵树,让你记录树上两点距离为k的点对数。 思路: dp[i][j]代表考虑i这颗子树,与它距离为j的点数量,dp[i][0]就是1了,然后dfs处理一下就可以,那么它就是答案的一部分,还有一部分就是把i当做中转节点,从u开始递归,枚举它的每个子树,ans+=(dp[u][tt]-dp[j...
2020-12-17
0
499
K - Appleman and Tree
题意: 给定一棵树,将树分成k个连通块,并且每个连通块内只有一个节点的方案数。 思路: 这个实在是想不出来啊,标解是开个dp[u][2]数组,表示只考虑u这颗子树并且u这个节点是否在有黑棋子的连通块中的方案数。 初始化就是如果黑色dp[u][1]=1,否则dp[u][0]=1; 转移也很骚: 枚举每...
2020-12-17
0
400
积蓄程度
题意:找一个点作为源点,问能往周围流的最多的水流。树形dp,dp数组代表以i为根的能流的所有水流,转移很简单,看代码,然后我们要处理一下从父节点流下来的值。如图。 之前wa了三十分钟,是因为转移的时候忘记考虑了父节点子树给他的贡献,从上面留下来的水流包括父节点父节点流下来的水流+子树的水流,然后别...
2020-12-17
0
392
金字塔
题意:给你一个字符串,问你有多少个树形结构。 思路:有dfs序那味道了,哈哈哈哈,然而是个区间dp,f[l][r]代表字符串从l到r中有多少种树形结构,状态转移不太好想,为了达到不重不漏的目的,我们通过枚举k来枚举第一个子树出现的大小,然后,只有在两端点相等的时候才能执行,因为最后要回到该点。其实k...
2020-12-17
0
0
首页
上一页
1
2
3
4
5
6
7
下一页
末页