boxxxx

算法

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

/ 注册

全部文章 / 算法（共38篇）

洛谷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

hdu1045 行列缩点+二分图匹配

题意：目标是尽可能多地在城市中设置碉堡，这样就不会有两个碉堡相互摧毁。如果没有两个碉堡在地图的同一水平行或垂直列上，除非至少有一个墙将它们分开，否则碉堡的配置是合法的。在这个问题中，我们将考虑小方形城市（最多4x4），其中包含无法穿过子弹的墙壁。下图显示了同一块板的五张图片。第一张图片是空白板，第...

2019-09-21

0 483

hdu2255 KM（带权二分图匹配）

这道题就是一个裸的带权二分图(KM)匹配模板。首先关于KM算法，我概念是看的这个视频（在2P） https://www.bilibili.com/video/av60813417/?p=2&t=316 然后关于代码方面我是看的这个博客 https://blog.csdn.net/frank...

2019-09-21

0 570

hdu2444 染色法+二分图匹配

有n个关系，他们之间某些人相互认识。这样的人有m对。你需要把人分成2组，使得每组人内部之间是相互不认识的。如果可以，就可以安排他们住宿了。安排住宿时，住在一个房间的两个人应该相互认识。最多的能有多少个房间住宿的两个相互认识。首先题目是要问能不能分成两组，每组人之间互相不认识，每个人只与对面...

2019-09-21

0 495

洛谷p1062 找规律

看题解都是进制转换，本弱弱一开始没想到，但是搞出了点规律，一样可以过。上图规律就是第 2^n 个数字就是数字 k^n; 然后在第 2^n 到 2^n +1之间的数字，就是第 2^n 的数加上第一个数，第二个数,知道第2^n-1个数。然后我们只要把这个过程模拟出来就可以啦，代码也很短 #inc...

2019-09-20

0 437

洛谷p2055 二分图匹配

题目描述学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 ...

2019-09-20

0 627