寒江陪烟火🔥

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篇）

HDU1054 Strategic Game（树形dp）

题意：给出一棵树，要求找到最少放几个士兵才能将所有点都看守到，每个节点的士兵只能看守临近一个的节点思路：简单的树形dp，往下扫一次就好了二分图也可做，应该不如树形dp快 /* *********************************************** A...

2016-03-23

0 277

HDU1011 Starship Troopers（树形dp）

题意：有n个房间组成一棵树，你有m个士兵，从1号房间开始让士兵向相邻的房间出发，每个房间里有一个代价，代价是值/20个士兵，同时有一个价值，问你花费这m个士兵可以得到的最大价值是多少，思路： dp[i][j]记录以节点i为根节点，j个士兵时所能够获得的最大价值 /* *****...

2016-03-23

0 299

HDU2196 Computer（树形dp）

题意：求树中每个点到所有叶子节点的距离的最大值是多少。思路：由于刚学树形dp，就参考了斌巨的博客连接：http://www.cnblogs.com/kuangbin/archive/2012/08/28/2659915.html 代码： /* ***************...

2016-03-21

0 351

HDU1520 Anniversary party（树形dp入门题）

题意：给定一棵关系树，每个节点有个权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？思路： dp[i][1]表示选，dp[i][0]表示不选则状态转移方程为： dp[i][1]+=dp[j][0]; dp[i][0]+=max(dp[j][1],dp[j][0]); A...

2016-03-20

0 300

HDU2476 String painter（区间dp）

题意：可以拿刷子刷s1，可以将任意区间刷成任意字母。问最少刷多少遍才能把s1刷成s2。思路：这道题太难想了（本人太弱）。。能想到是区间dp，想了半天都没法转移状态。最后看了看网上个大神牛的博客，才恍然大悟。。思路就是先用dp记一下空白串到s2串需要刷的次数，然后再刷s1串到s2串...

2016-03-20

0 221

HDU4283 You Are the One（区间dp）

题意：有n个选手，每个人都有一个愤怒值a[i]，当第i位选手是第k个出场的时候，他的愤怒值为(k-1)*a[i]; 有一个黑箱子（堆栈），可以往里面放人（改变出场次序），问最小的愤怒值。解析： dp[i][j]保存的是i到j之间最大的愤怒值减小量。假设第i个人第k个上场，那么后面第i...

2016-03-19

0 226

CodeForces 149D Coloring Brackets（区间dp）

题意：给一个给定括号序列，给该括号上色，上色有三个要求 1、只有三种上色方案，不上色，上红色，上蓝色 2、每对括号必须只能给其中的一个上色 3、相邻的两个不能上同色，可以都不上色求0-len-1这一区间内有多少种上色方案我按最基本的区间dp思路果断跑了810ms，看了别人30ms的...

2016-03-19

0 337

HDU1078 FatMouse and Cheese（记忆化搜索）

题意：老鼠每次只能走k步停下来，停下的这个位置只能比上一个停留的位置大，并获取其价值，每次只能水平或垂直走（十字），问最大能得到的价值 #include <iostream> #include <algorithm> #include <cs...

2016-03-17

0 264

POJ1458 Common Subsequence（最长公共子序列）

#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <stack> #in...

2016-03-17

0 294

QDU68 UP UP UP!（最长上升子序列个数）

<label class="problem-label">描述</label> 题意很简单，给你长度为n的序列，找出有多少个不同的长度为m的严格上升子序列。（PS：相同子序列的定义为，每一个元素对应的下标都相同） ...

2016-01-04

0 266