寒江陪烟火🔥
寒江陪烟火🔥
全部文章
dp
acm相关(6)
RMQ(5)
STL(6)
主席树(2)
二分匹配(23)
二分查找(2)
分治法(3)
划分树(1)
单调队列(2)
博弈(11)
字典树(3)
字符串处理(1)
学习(1)
并查集(4)
强联通分量(3)
归并排序(1)
拓扑排序(1)
搜索(1)
数论(8)
最小生成树(3)
最短路(5)
树状数组(7)
树链剖分(4)
欧拉回路(5)
简单模版(14)
简单题(24)
线段树(13)
网络流(6)
归档
标签
去牛客网
登录
/
注册
寒江陪烟火🔥的博客
全部文章
/ dp
(共68篇)
hihocoder1200 Increase Charisma Points(二进制log拆解答案)
题意: 给定一张N个点的完全图,可以从任何一个点出发,同一个点可以经过多次。询问总路径长度不超过M的情况下,最多能够经过多少个点。 思路: 首先我们能够想到一个最简单的模拟算法。 建立数组dist[][],dist[i][j]表示经过i个点后,最后停留在j所以经过的最短路径长度。 那么有如...
2016-09-06
0
275
hihocoder1238 Total Highway Distance(树形dp)
题意: 给定一颗有N个节点的带权树,之后进行M次操作: Q操作:询问树上所有点对之间的距离之和 E操作:修改树上某一条边的权值 思路: 树形dp求出每条边被利用的次数并统计 然后修改的时候就把这个边权修改并将改变值乘上利用次数更改ans /* **********...
2016-09-04
0
230
HDU5807 Keep In Touch(分段式dp)
题意: 在Byteland一共有n个城市,编号依次为1到n,同时有m条单向道路连接着这些城市,其中第i条道路的起点为ui,终点为vi(1≤ui<vi≤n)。 特工团队一共有3名成员:007,008,以及009,他们将要执行q次秘密任务。 在每次任务中,三人可能会处于...
2016-08-07
0
194
BZOJ4509 Angry Cows(dp)
题意: 大概就是一条线上有n个炸弹,然后让你随意扔一个爆炸半径为r的炸弹使他们全部爆炸, 第一次被引爆的炸弹爆炸半径为r-1,第二次为r-2。。。 求r最小是多少 思路: 用两个数组处理得到从左往右和从右往左到当前炸弹时的爆炸半径最小是多少,然后枚举投弹位置就可以了 /* ****...
2016-08-06
0
198
HDU3449 Consumer(依赖背包)
参考:http://www.cnblogs.com/wuyiqi/archive/2011/11/26/2264283.html 题意: 有n个箱子,每个箱子里装有一些物品 要买这些物品就要先买这个箱子 这就符合依赖背包的条件了 要想买b就必须买a 思路: 先写二维的,dp[i][j]...
2016-07-29
0
200
HDU5773 The All-purpose Zero(LIS)
题意: 给你一个长度为10W的数组,每个数范围0-100W 其中的0可以变为INT范围内的任意值 问最长上升子序列的长度 思路: 这题当时水过了。。数据太水 比赛结束了看了题解,简直膜拜神思路。。 0可以转化成任意整数,包括负数, 显然求LIS时尽量把0都放进去必定是正确的。 因此...
2016-07-28
0
247
codeforces 700B Connecting Universities
题意: 给你一棵树,边权均为1,上面有2K个点为学校 让你将学校配对,配对的学校需要修路连接 问修的路最长为多少 思路: 每条边计算最大价值 即这条边两端学校中较小的那个数量 因为最大利用这条边就要把两端的学校配对 较少的那端的学校全都配对过去,就全都走了这条路 然后把每个边的价值...
2016-07-25
0
265
HDU3107 Godfather(树的重心)
题意: 给你一棵树,求树的所有重心并按字典序输出 思路: 树形dp找一遍,把重心记到一个数组里,最后sort一下 这个题用vector居然超时。。。。。。 这让习惯用vector的人瞬间感觉就不好了。。 /* ************************************...
2016-07-25
0
181
POJ1655 Balancing Act(树的重心)
题意: 给你一棵树,求树的重心 如果有多个就输出序号最小的 思路: 树的重心就是以它为根的所有子树中节点最多的节点数最小 树形dp轻松可以解决 /* *********************************************** Author :dev...
2016-07-25
0
200
UPCOJ2012 The King’s Walk(dp)
题意: 给你一个n*n的地图,起始位置和目标位置 你每次可以八向走 问你有多少种最少步数到达的方案 答案取模 思路: 走的步数是确定的,是横坐标、纵坐标只差较大的那个 然后就是用确定的步数走另一个坐标差这样的距离 每次可以不走,前进一步,后退一步,不超出地图范围即可 这尼玛简直看出...
2016-06-10
0
247
首页
上一页
1
2
3
4
5
6
7
下一页
末页