题目链接：hdu6570 题目大意（机翻）: Avin正在研究系列。 如果满足以下条件，则一个系列称为“波动”： 1）它至少包含两个元素； 2）所有位于奇数位置的元素都相同； 3）偶数位置的所有元素都相同； 4）奇数位置的元素与偶数位置的元素不同。 您得到的序列长度为n。 Avin要求您找到最长的“波浪”子系列。 子系列是系列的子序列。 第一眼看见，我就觉得他是个dp（看题解才知道暴力也行）； 我是这么考虑的在一开始 f[i][j][0/1]： 表示的是选取了第i个数字后是奇数长度还是偶数长度， 然后如果当前长度是奇数，则j代表偶数位置的数的大小是j，如果当前长度是偶数则同理。（0代表链长为...

题目链接：hdu6736 这个题目由于题目对于给的图有很严重的限制，就是每个边最多只能处于一个简单的循环中，那么其实对于所有的图，都会是那种有一条链，链上的节点有个简单环，简单环的节点又有一条链如此反复。 通过分析其实就可以知道，对于每一个边数为n的环，让他变成树的方案数目是2^n -1;就是拆一条的方案+拆2条+。。。。+拆n条。 对于每一条单独的链，让他变成树的方案数是2^n ，因为链的话可以不用拆也是一种情况。那么答案就是乘上所有的环的方案数目在乘上所有链的方案数目。由于链的方案数最后是乘法所以你所有链的方案数就是所有链的边数的总和为n，链能给出的答案也是 2^n ; 也就是我们只要算...

传送门：hdu6739 题目就是有很多种技能，想要用某种技能需要集齐某些含有QWE的组合（无序组合），题目就问给你一个按出技能的一个顺序，叫你最少按几次技能可以按出这些技能，（每集齐一个技能的组合要释放还需要按一次R）； 这就是一道动态规划的题目，不要被题目骗了，虽然技能要按出来只需要一个无序组合，但是由于你这个按的顺序的不同会导致后面按的次数的不同，所以还是要把他当做有序去看，也就是一个技能比如要集齐QWE才能放。 就把他当做，QWE,QEW,WQE,WEQ,EQW,EWQ才能放也就是一种技能有6种组合可以把他按出来。 再由于题目说明的你只能存在3个技能，再按一个会把第一次按的技能挤掉。所以...

题目链接：洛谷p4178 这道题目是点分治的题目，与模板题不一样的是，这是要统计小于路径长度为k的点对数。我们分析下与模板题的区别，模板要求的是路径等于k的长度的路径是否存在，然后统计的方法是对于每个重心（跟），求出各点与根的路径，然后重心下面的各个子树中，相同的子树不去统计答案，去计算之前非该子树的路径能否凑出k的路径，也就是吧路径分成了（当前子树的路径与非当前子树的路径），然后其实我们也可以利用这个模板题的思想，一旦当前子树的路径与非当前子树的路径能凑出小于k的路径，那么这就是一个就是符合条件的点对，我们可以对于每种路径的数目去记录一下，就是记录有多少条路径可以达到这个路径数，但是答案就是...

题目链接：洛谷p1006 题目就是说传两次纸条，一次从左上传到右下，一次从右下传到左上，路径不能重复，其实我们换个角度就是从左上传到右下传两次就可以了。 借助洛谷大佬题解的一张图 你传两次的路径，每一步两个点的连线一定在一条斜线上，那么，其实对于一个矩阵，也就最多只有n+m条斜线，已确定两点在一条线上，那么就比较容易去设计。 我们用f[sum][i][j]，sum表示当前斜线是哪条（就是斜线上任何一个点的横竖坐标的累加，比如sum = 3就是图里面那条斜线），i表示一个人当前走的列的坐标，j表示另一个人当前走的列的坐标。 ij肯定不能相当（因为是在一条线上）。 我们如何转移呢？ 思考一下我们是...

题目链接hdu6579 题目就是给你你个序列，问你任意区间内去取数，要求这些数的异或和最大，还要求可以增加这个序列。 从序列里面取数求异或和最大，这个是线性基模板题，但是题目要求的不一样，要的是任意区间。要怎么处理呢？就是我们开一个二维的线性基，f[i][j], i表示的是f[i]这一维的线性基是[1,i]的。 但是这只是解决了右端点，但是左端点怎么办？那么其实就是对于[1,i]这个区间的线性基的数目是固定的，但是数的组合可以有很多种，所以我们在插入线性基的时候，线性基同一个位置的数，如果这个数的位置比当前这个数的位置要小，则交换。就是这个位置的线性基替换成位置比较大的数就可以了。最后得答案只...

题目链接： 洛谷p1220 这道题是个dp的题目，首先我们就要考虑，老张去关路灯，存不存在一种情况就是我人在3的位置，我去走到5关灯，在走到4去关4的灯。这是不可能存在的是不是，也就是说关灯只会是从已经关好灯的区间去延伸一个单位，假设我们目前在3 的位置，那么我们接下来关的下一盏灯就是2或者是4.换一种表达就是，当前已经关好灯的区间是[3,3],那么我们下一步关完灯后就只可能是[2,3]或者是[3,4]，就是所在区间的左端点去-1，或者右端点去+1;如果我们设计状态是 f[i][j] 表示关完[i,j]这个区间的灯所花费的最少价值的话，那么从起点处去转移状态，答案应该就是f[1][n]; 怎...

传送门：洛谷p1373 这道题我原本的想法就是很简单的f[i][j][x][y][0/1];就是以第i，j格为终点的方案数目，可是即wa又mle ，最后看了看题解才比较了解。就是我们不去储存两个人瓶子各自有多少，而是去去一个差值，然后差值取模后相等的都是等价的，这里的取模是对k+1取模，因为瓶子差值就是[0,k]，所以对k+1取模。 用f[i][j][p][0/1]表示以ij结束的格子差值为p的由0或者1走到这一格子的方案数目。(0表示小a走的，1表示小b走的) 然后我们去对每个ij枚举他们瓶子的差值p 也就是 f[i][j][p][0]+=f[i-1][j][(p-value[i][j]+k...

题意：场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。 设计一个程序，计算Jimmy到底地面时可能的最早时间。 这是一道DP问题，首先是要分析每一步的转态，首先我们很容易想到对于每一个平台，我们往左走可以到达平台和往右走可以到达的平台是确定的。我们就可以先预处理出这一部分。接着我们考...

题意：现在有n个人要买电影票，如果知道每个人单独买票花费的时间，还有和前一个人一起买花费的时间，问最少花多长时间可以全部买完票。 刚学DP，就从简单的开始做起，从这道题我们可以知道，每个人只有三种情况，如下图，f[i][1/2/3]表示第i个人选择哪种购买方式所能得到最少的钱。 解释下转移方程，因为如果那个人选择了自己买，那么知道这个人所能获得的最少价值就是前面一个人（i-1）个人选择他自己买，或者选择和前面的人一起买的最少价值,再加上i这个人自己买的价值。 所以f[i][1] = min(f[i-1][1],f[i-1][2])+v[i]; 先说下第三种，就是当前的人跟后面的人一起买，所以他...

题目就是给你一个n点的树，每条边权值为1，对于每个点，求出离这个点距离不超过k的点的个数，然后答案是输出每个点的答案的异或和。 分析，首先他是要求每个点距离不超过k的点数，对于每个点，这个不超过距离k的点数，我们可以从下面（就是这个点的子树去找）， 也可以从这个点的上方去找。 我们分别去考虑。 用f[i][k] 表示从i这个点往下符合条件（距离为k）的点的答案。 对于每个点，先去得到他子树去找到的所有的点。这个就是很经典的树dp做法了，就是去一遍dfs从叶子节点往上去递归回溯更新答案。最底层就是f[i][0~k] = 1;（i是叶子节点）因为从0到k的距离都是只有他本身。对于非叶子节点，我们要...

题意：目标是尽可能多地在城市中设置碉堡，这样就不会有两个碉堡相互摧毁。如果没有两个碉堡在地图的同一水平行或垂直列上，除非至少有一个墙将它们分开，否则碉堡的配置是合法的。在这个问题中，我们将考虑小方形城市（最多4x4），其中包含无法穿过子弹的墙壁。 下图显示了同一块板的五张图片。第一张图片是空白板，第二张和第三张图片显示合法配置，第四张和第五张图片显示非法配置。对于该板，合法配置中的最大块仓数为5; 第二张图片显示了一种方法，但还有其他几种方法。 您的任务是编写一个程序，在给定地图描述的情况下，计算可以在合法配置中放置在城市中的最大数量的阻止房屋。 分析：一开始看见这题我并不是很知道怎么写，不...

这道题就是一个裸的带权二分图(KM)匹配模板。 首先关于KM算法，我概念是看的这个视频（在2P） https://www.bilibili.com/video/av60813417/?p=2&t=316 然后关于代码方面我是看的这个博客 https://blog.csdn.net/frankax/article/details/81541421 都是感觉非常不错。 然后直接写模板就可以了。 #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #i...

有n个关系，他们之间某些人相互认识。这样的人有m对。 你需要把人分成2组，使得每组人内部之间是相互不认识的。 如果可以，就可以安排他们住宿了。安排住宿时，住在一个房间的两个人应该相互认识。 最多的能有多少个房间住宿的两个相互认识。 首先题目是要问能不能分成两组，每组人之间互相不认识，每个人只与对面那部分的人认识。这个就是要判断是不是能构成一个二分图的样子。 判断二分图我们使用染色法，就是规定一个点的颜色，然后与其相连的点的颜色是不同的，如果遇到了无法满足的情况，（比如之前颜色是1 ， 但是到现在你又要这个点颜色是2就无法满足）。判断是二分图后，直接二分图匹配模板就可以了。还有个小问题就是，我...