boxxxx

分类

学习(10) 并查集(1) 数位dp(1) 概率dp(1) 算法(38) 线性dp(1) 题解(3)

/ 注册

全部文章（共55篇）

hdu 6736 dfs

题目链接：hdu6736 这个题目由于题目对于给的图有很严重的限制，就是每个边最多只能处于一个简单的循环中，那么其实对于所有的图，都会是那种有一条链，链上的节点有个简单环，简单环的节点又有一条链如此反复。通过分析其实就可以知道，对于每一个边数为n的环，让他变成树的方案数目是2^n -1;就是拆一...

2019-10-18

0 435

hdu6739 dp

传送门：hdu6739 题目就是有很多种技能，想要用某种技能需要集齐某些含有QWE的组合（无序组合），题目就问给你一个按出技能的一个顺序，叫你最少按几次技能可以按出这些技能，（每集齐一个技能的组合要释放还需要按一次R）；这就是一道动态规划的题目，不要被题目骗了，虽然技能要按出来只需要一个无序组合，...

2019-10-18

0 423

洛谷p4178 点分治+线段树

题目链接：洛谷p4178 这道题目是点分治的题目，与模板题不一样的是，这是要统计小于路径长度为k的点对数。我们分析下与模板题的区别，模板要求的是路径等于k的长度的路径是否存在，然后统计的方法是对于每个重心（跟），求出各点与根的路径，然后重心下面的各个子树中，相同的子树不去统计答案，去计算之前非该子树...

2019-10-14

0 415

洛谷p1006 DP

题目链接：洛谷p1006 题目就是说传两次纸条，一次从左上传到右下，一次从右下传到左上，路径不能重复，其实我们换个角度就是从左上传到右下传两次就可以了。借助洛谷大佬题解的一张图你传两次的路径，每一步两个点的连线一定在一条斜线上，那么，其实对于一个矩阵，也就最多只有n+m条斜线，已确定两点在一条线...

2019-10-13

0 492

hdu6579 线性基

题目链接hdu6579 题目就是给你你个序列，问你任意区间内去取数，要求这些数的异或和最大，还要求可以增加这个序列。从序列里面取数求异或和最大，这个是线性基模板题，但是题目要求的不一样，要的是任意区间。要怎么处理呢？就是我们开一个二维的线性基，f[i][j], i表示的是f[i]这一维的线性基是[...

2019-10-09

0 566

洛谷p1220 dp

题目链接：洛谷p1220 这道题是个dp的题目，首先我们就要考虑，老张去关路灯，存不存在一种情况就是我人在3的位置，我去走到5关灯，在走到4去关4的灯。这是不可能存在的是不是，也就是说关灯只会是从已经关好灯的区间去延伸一个单位，假设我们目前在3 的位置，那么我们接下来关的下一盏灯就是2或者是4....

2019-10-05

0 467

洛谷p1373 DP

传送门：洛谷p1373 这道题我原本的想法就是很简单的f[i][j][x][y][0/1];就是以第i，j格为终点的方案数目，可是即wa又mle ，最后看了看题解才比较了解。就是我们不去储存两个人瓶子各自有多少，而是去去一个差值，然后差值取模后相等的都是等价的，这里的取模是对k+1取模，因为瓶子差值...

2019-10-04

0 524

POJ1661 dp

题意：场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。J...

2019-09-26

0 494

hdu1260 DP

题意：现在有n个人要买电影票，如果知道每个人单独买票花费的时间，还有和前一个人一起买花费的时间，问最少花多长时间可以全部买完票。刚学DP，就从简单的开始做起，从这道题我们可以知道，每个人只有三种情况，如下图，f[i][1/2/3]表示第i个人选择哪种购买方式所能得到最少的钱。解释下转移方程，因为...

2019-09-26

0 461

hdu5593 树dp详解！！！

题目就是给你一个n点的树，每条边权值为1，对于每个点，求出离这个点距离不超过k的点的个数，然后答案是输出每个点的答案的异或和。分析，首先他是要求每个点距离不超过k的点数，对于每个点，这个不超过距离k的点数，我们可以从下面（就是这个点的子树去找），也可以从这个点的上方去找。我们分别去考虑。用f...

2019-09-22

0 505