Tag Archives: DP

[UVA11324]The Largest Clique

题意: 给一张有向图, 求一个结点数的最大集, 使得该结点集中任意两个结点 u 和 v 满足: 要么u 可以到达v, 要么v 可以到达 u (u 和 v相互可达…

2017年10月19日

[UVA10029] Edit Step Ladders

按照字典序给出一系列的字符串,让你从中找出一个子序列,使得子序列中的第 i 个字符串可以通过增删改一个字符得到第 i + 1 个字符串,问你满足条件的最长子序列…

2017年9月8日

POJ1661 Help Jimmy

Jimmy 落到一个平台后,要么向左,要么向右,对于任意一个平台都是这样。如果知道了 Jimmy 落到某一平台后的位置,向左或者向右到另外一个平台,这样就产生了…

2017年8月14日

bzoj1003 [ZJOI2006]物流运输trans

用 cost[i][j] 表示从第 i 天到第 j 天之间,从 A 点到 B 点的最短路。dp[i] 表示第 i 天的最小花费,那么就有 dp[i] = min…

2017年8月14日

POJ3616 Milking Time

给你n个区间,每个区间对应一个生产值,让你选出其中的某些区间,使得这些区间中,所选的任意两个相邻区间相差至少为r,并且这些区间的生产值和最大. 将区间按端点排序…

2017年8月13日

HDU1078 FatMouse and Cheese

一只老鼠在一个n*n的地图上吃食物,每次只能垂直或者水平走,且所走的格子上的食物必须大于当前所在格子的食物,每次前进,可以只走一格,也可以跳着走k格,最大不能超…

2017年8月13日

POJ3186 Treats for the Cows

给你一个含有n个数的队列,每次只能从队头或者队尾取出一个数,将第i次取出的数乘i,把所得结果都加起来,求取完所有的数能得到的最大值. 区间DP,定义 dp[i]…

2017年8月13日

HDU1087 Super Jumping! Jumping! Jumping!

给你一个n个数,让你在这n个数的所有递增子序列中找出一个和最大的递增子序列,把这个和输出. 就是最长递增子序列问题的变形.dp[i] = max(dp[i], …

2017年8月13日

HDU1160 FatMouse’s Speed

n个老鼠,分别给出这n个老鼠的质量和速度,让你选出其中的k个老鼠,使得这k个老鼠的质量按严格递增排列,速度按严格递减排列. 将其中一个速度字段递减排序,然后求质…

2017年8月13日

HDU1114 Piggy-Bank

有个储存罐,没硬币时重量为e,有硬币时重量为f,另给出n个硬币的质量和分值,求这个储存罐最少装有多少钱? 因为一个储存罐中可以装很多相同的硬币,因此可以判断这是…

2017年8月12日