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篇)
线性dp
题目背景 建筑大师最近在跟着数学大师 ljt12138 学数学,今天他学了等差数列,ljt12138 决定给他留一道练习题。 题目描述 ljt12138 首先建了 nn 个特斯拉电磁塔,这些电塔排成一排,从左到右依次标号为 11 到 nn ,第 ii 个电塔的高度为 h[i]h[i] 。 建筑大...
2020-12-17
0
579
Maximum White Subtree
解题报告: 这题感觉是树形dp,但想不出来怎么做,看了题解,题解的意思是先从根开始dfs用子树的信息更新根,f数组先定义出包括i的子树中最大的白点减去黑点,由于黑点是0我们可以把它变成-1,那么就是等价于求子树的最大和,然后递归完,除了根以外,每个点都成为过儿子节点,那么我们要考虑根节点对他的影响啦...
2020-12-17
0
416
New Year Parties
题意给定你n个点,每个点可以停在原地或者向左向右,问最多能有多少个不重合的点 还有 最少能有多少个点。 解题报告:看题目就感觉是dp题 但听大佬说不能dp做? 但我抱着侥幸的心里写了写dp,一开始确实wa了,后来看了看状态转移 ,我们dp数组定义的是考虑前i个人并且第i个人的状态是向左、向右、不动 ...
2020-12-17
0
337
清理班次
农民约翰正在指挥他的N头牛进行清理工作。 他将一天划分为了T个班次(1~T)。 每头牛都只能在一天中的某一个时间段内进行不间断的工作。 你需要帮助约翰排列出一个合理的奶牛的清理班次,使得每个班次都有奶牛在进行清理,而且动用的奶牛数量可以尽可能的少。 输入格式 第1行:两个空格隔开的整数N和T...
2020-12-17
0
456
张老师的旅行 区间dp
区间dp,由于n很小,开两维,然后外加一维,最后遍历完所有区间内的点停在最左边还是最右边。 #include<stdio.h> #include<string.h> #include<algorithm> #include<map> #include...
2020-12-17
0
382
2020CCPC秦皇岛 k Kingdom’s Power
题意:有无数个军队可以从树根1出发,每花费一个点可以让军队走一步,问遍历完整个树的最小花费。 思路:先记录每个节点的高度,用节点根据它子树的高度的高度来排序,然后节点的高度为子树的最高高度+1,然后类似树形dp,从上往下递归h和与从下往上走的值取min。最后把所以的根节点的值加起来。 #inclu...
2020-12-17
0
524
CF229D Towers
来自专栏
题意是:每次操作能将某个数加到隔壁的数上面,最后求最少操作数,使得序列是非递减序列。 思路:我们发现每次可以将l~r之间的区间合并成一个数,然后需要r-l次操作,我们设定从f[i]为从1处理到i并且序列是递增的最少操作数,然后枚举i是在哪一段区间里,维护l[i](在不影响f[i]最优值的情况下l[i...
2020-12-17
0
677
CF1407D Discrete Centrifugal Jumps dp
来自专栏
题意:如图 思路:单调栈维护某个点的前驱节点有多少个,设置f[i],定义为跳到i这个位置最少跳的次数。然后我们考虑一下什么时候可以跳 1:两边比中间都大,并且左边比右边大 2:两边比中间大,并且右边比左边大 3:两边比中间小,并且右边比左边大 4:两边比中间小,并且左边比右边大。维护四个单调栈。 ...
2020-12-17
0
844
数位dp变相 [HDU-5456]
题意:给你n个火柴 让你凑成a-b=c的形式,不包括前导0,问总共有多少个方案数(mod上m)。 思路:真的想不出来,太妙了,先把a-b=c变形成a=b+c,然后从低位往高位枚举每位填的数,dp状态定义成f[i][f1][f2][flow] (只剩下i根火柴,b是否填完,c是否填完,是否有进位的方案...
2020-12-17
0
515
(我上绿了)Hills
纪念一下自己上绿了。 下面是题目: 题意:当一个数满足大于他相邻的数的时候,可以在他这建房子,我们每次操作可以将某个数减1,问最少操作多少次可以满足(1~(n+1)/2)。 思路: 一开始想的是定义状态是f[i][j]表示考虑前i个建立j个房子的最小操作数,后来发现好像不够,因为我们很难判断出第...
2020-12-17
0
482
首页
上一页
1
2
3
4
5
6
7
下一页
末页