寒江陪烟火🔥
寒江陪烟火🔥
全部文章
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篇)
POJ1741 Tree(树分治)
题意: 求树上距离小于等于K的点对有多少个 思路: 每次分治,我们首先算出重心,为了计算重心,需要进行两次dfs,第一次把以每个结点为根的子树大小求出来,第二次是从这些结点中找重心 找到重心后,需要统计所有结点到重心的距离,看其中有多少对小于等于K 但是这些求出来满足小于等于K的里面只有...
2016-10-22
0
250
codeforces713D Animals and Puzzle(二维倍增)
引自:http://www.cnblogs.com/qscqesze/p/5929117.html 题意: 给你一个01矩阵,然后Q次询问,每次询问一个矩形区域中,最大的全一正方形的边长是多少。 思路: 首先考虑Dp,dp[i][j]表示以(i,j)位置为右下角,最大的正方形边长是多少,显然...
2016-10-14
0
291
codeforces713C Sonya and Problem Wihtout a Legend(dp)
题意: 给你一个序列,你可以改变任意一个数字的大小,代价是改变量 问你使其变成严格单调递增序列的最小代价 思路: 单调不减的最小代价可以用O(n^2)的时间搞出来,而让单调递增转化为单调不减只需要让a[i]-i就可以了 /* *********************...
2016-10-14
0
255
codeforces724E Goods transportation(最小割——dp)
题意: 原点汇点连所有的,流量给出,左边点连右边的,流量为c,问最大流 思路: /* *********************************************** Author :devil ********************************...
2016-10-11
0
350
codeforces710E Generate a String(dp)
题意: 给你一个n(1e7),和x,y 每次可以+1/-1/*2 +-花费x,*2花费y 问你从0变到n的最小花费 思路: 关键是n小啊~ 对于每个i,他可能是由i-1加了1 或者i/2乘了2得来的 当前是奇数的时候,可能是i/2*2+1或者(i/2+1)*2-1得来的 前者在i...
2016-10-10
0
217
hihocoder1386 Pick Your Players(dp)
题意: 你需要买一个足球队(11个球员),每个球员有位置、价值。花费,有以下限制: 位置分为前锋(1-3人)、中腰(2-5)、后卫(3-5)、守门员(1) 每个人有 value,总的 value 是每个人的value加起来 ,选一个队长,队长的加两次 每个人有个 cost,总花费不能超过给定值 求...
2016-09-29
0
260
hdu5900 QSC and Master(区间dp)
题意: 给你一个长为300的序列,每个位置有个代号和价值 如果相邻两个位置的代号不互质就可以得到他们的价值和并移除他们 问最大价值 思路: 区间dp,n才100,直接n*3就可以 /* *********************************************** ...
2016-09-21
0
216
hdu5898 odd-even number(数位dp)
题意: 求L到R区间内,连续奇数个数是偶数,连续偶数个数是奇数的数的个数 思路: 裸数位dp,赛场上忘了不合法的break,妈的调了一个多小时简直是日了狗了! 本来就是蒟蒻还感冒了什么题都写不出来 /* *************************************...
2016-09-21
0
179
bzoj1003 物流运输(dijkstra+dp)
题意: 一共有n天,每天都要把货物从1运到m,代价是路长 然后每个地方都可能有几天不能走 然后你就必须改变路线在那天避开这些地方,这需要代价k 问你n天的最小代价 思路: 一共最多100天,可以n^2暴力时间段,表示这段时间的路径是一样的 然后跑dijkstra,得出最优解 然后用d...
2016-09-08
0
262
hihocoder1199 Tower Defense Game(树形dp)
题意: 给定一颗以1为根节点的树,每个节点有一个购入价格p和卖出价格q。 进入一个节点时需要花费p,离开时可以收回q,每个节点只产生一次购入和卖出。 请你选择一个遍历的顺序,要求在遍历的过程中身上的钱数不小于0,且出发时带的钱数最少。 按照遍历的顺序是指:当你选择了一颗子树之后,你需要将这个...
2016-09-06
0
215
首页
上一页
1
2
3
4
5
6
7
下一页
末页