51nod1720祖玛这又是一个区间dp，但这题又和其他的不一样，这题又用记忆化搜索，但是多学一种方法也没事，但其实用搜索后就模拟即可了。#include<bits/stdc++.h>usingnamespacestd;//定义全局变量intn;//数组长度intdp[505][505];//dp[l][r]表示在区间[l,r]之间的

51nod3180矩阵连乘感觉区间dp还是要感性理解，但好像区间有套路的，这和石子合并很像，就根据题意模拟。这个写法的区间比较巧妙，左右同时增加，相当于滑动窗口，因为一开始花费一个是0，所以注意dp的初始化。#include<bits/stdc++.h>usingnamespacestd;intn;

学习笔记最大M子段和V1\(N\)个整数组成的序列\(a[1],a[2],a[3],…,a[n]\)，将这N个数划分为互不相交的\(M\)个子段，并且这\(M\)个子段的和是最大的。如果\(M>=N\)个数中正数的个数，那么输出所有正数的和。\(N,M<=5000\)。例如：\(-211-413-56-2\)，分为\(2\)段，\(11

51nod1051最大子矩阵和可以用前缀和容斥优化到\(O(n^4)\)，但是不够进行如下图操作：将每一列的数值都压缩到一维的数组上，就转换为求最大字段和问题，时间复杂度\(O(n^3)\)。看看代码就知道了。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,m;

51nod1243排船的问题求最长绳子最短，考虑二分答案，判断时我们优先向左放，看是否能全放下。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,x,m;intpos[50005];intcheck(intmid){ intp=x;//偏差地图 intx2=x*2; intmx=m+x;//偏差地图

51nod1020逆序排列学习笔记其实要预处理，但唐的我非要每次都求一遍。设状态为\(dp[i][j]\)选了i个数逆序对数为j的排序种类数。首先初始化\(dp[i][0]=1\)即没有逆序对，转移方程\(dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+……+dp[i-1][j-i]\)这是显然的（放上这个数，会产生的

题目链接学习链接设状态\(dp[i][j]\)表示整数\([1,i]\)满足要求的排列中，最后一个数选\(j\)的排列数。开一个数组记录他的状态：把前面已选好的序列中大于等于\(j\)的数都加一后再把\(j\)加到后面。#include<bits/stdc++.h>usingnamespacestd;#definelllong

51nod1050循环数组最大子段和虽然是板子题，两种做法，我们先写一种，另一个咕咕。因为是循环，所以分为两种，中间的和两边的，中间的直接dp求最大，两边的转化一下就是总的数字和减去中间的最小数字和。#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglla[500005]

51nod1791原题链接因为在括号串固定的情况下，括号的匹配是固定不变的。所以对左括号进行匹配，p[i]表示与i这个括号相匹配的括号的位置，易得到dp方程ans[i]=ans[p[i]+1]+1,然后再从后先前一遍求和即可。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconst

可以发现步数限制把数轴变为了环。环之间不可以交换，环内相邻两点可以交换，然后我们只需要对每个环操作，最后累加。对于环上的每个石子堆，我们需要将其石子数调整到均值\(avg\)。因此，我们首先计算每个堆石子相对于\(avg\)的偏差，即\(nowa[i]-avg\)。因为相邻节点不一定能凑齐

51nod1110距离之和最小考虑贪心取中位数，因为中位数到左边的点和右边的点的个数相同，更合理，权值的话可以转化为一个单点，然后没了。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn;structss{ llx,w;}a[100005];boolcmp(ssg,ssh){ return

整数分解为2的幂这题非常厉害，建议认真看下去虽然我讲的也不好。首先肯定先想到的是多重背包，可以把每个次幂当作物品，然后套板子。但是这题有\(O(n)\)复杂度的做法，我们想如果一个数\(i\)是奇数，那他只能由\((i-1)+1\)转化过来（2的幂次只有1是奇数），那方案数就是\(i-1\)的方案

争渡原题链接常记溪亭日暮，沉醉不知归路。兴尽晚回舟，误入藕花深处。争渡，争渡，惊起一滩鸥鹭。——李清照《如梦令·常记溪亭日暮》给出线段上界和下界，要在严格递增地在区间内选数，问到最后一条线段的方案数。见上图，第\(i\)条线段\(j\)点的方案数为\(i-1\)条线段的\(j-1\)

原题链接这题因为要求满足t时间内，所以用dp，不过我们的状态比较特殊，\(dp[i][j]\)表示到\(i\)点时经过\(j\)个点的最短时间，因为题目为DAG所以要用拓扑排序，每到一个点，枚举所有出边，更新出点的状态\(f[v][j+1]=min(f[v][j+1],f[u][j])\)，最后的答案就是所有\(f[t][j]\let

51nod1366贫富差距这题题面挺抽象的，一个人与他所以的朋友的钱不能超过\(d\)，问朋友链上钱最多的人的钱与钱最少的人的钱相差多少，求差距的最大值。如果两个人不属于同一个连通块那么差距可以无穷大，好了特殊情况解决了。然后为了使这个差距最大，那么对于每个朋友我们都取\(d\)

3179绝世好题他仅仅要求序列最长的长度，我们可以引用最长上升子序列的思想（有些隐蔽），设状态\(dp[i]\)为二进制第i位为1的最长序列长度，对于一个数10101\(dp[1],dp[3],dp[5]\)都应该加一，对他们的数值取个最大值，并将他们的状态与最大值比较更新。下列代码为上述思路：#includ

暴力构图为\(O(n^2)\)无法实现，但可以发现有些边无用，可以先按x排序，第i号点与第i+1号点一定最近，所以建一条边，y坐标同理，然后跑最短路即可自动选择\(min(|x_1-x_2|,|y_1-y_2|)\)#include<bits/stdc++.h>usingnamespacestd;constlonglongINF=0x3f3f3f3f;constint

闲话虽然这题好像找不到原题了，但毋庸置疑地说这的确是并查集的好题。分析可以先对奇偶区间进行分析，当这个有偶数个1时，区间\(1-(left-1)\)一定与区间\(1-right\)的奇偶性相同。如此图\(3-4\)为偶区间，根据分析，\(1-2\)为奇区间。\(1-4\)也为奇区间。但如果填入的

问题1-Pinball为什么这样解释的通，我看不懂什么意思？还有这个\(e\)在后面状态中没有体现。具体做法？为什么只有\([a_i,c_i]\)需要考虑？他可以往左边掉。那么从\(n\)开始掉又如何考虑Kamp手绘的图：这个图似乎就不满足了。不知道什么意思。这个思路怎么做。

51nod-基因匹配+luogu-【模板】最长公共子序列本题重在转化。由于最长公共子序列的下标是一个最长上升子序列，所以我们可以考虑把数字映射成下标，有多个就要倒序把每个值映射成多个不同的值，因为一个数有多种下标都是可取的。51nod-3976-最长序列与基本问题相同，但是需要根据长度插

https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338https://class.51nod.com/Html/Textbook/Problem.html#problemId=3928&textbookChapterId=725保证右端点为\(n\)是因为如果不是这样操作，可能导致后面的数大小关系发生变化，而如果保证了

https://class.51nod.com/Html/Textbook/Problem.html#problemId=3986&textbookChapterId=725https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338我们将馅饼表示为\((p_i,t_i)\)，即一个平面直角坐标系上的点。我们把馅饼看成静止，人每次往

https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338https://class.51nod.com/Html/Textbook/Problem.html#problemId=3976&textbookChapterId=725LIS是符号只有大于或小于，所以这道题就是LIS问题。状态设计同LIS，由于答案就是长度，所以就能知

https://www.luogu.com.cn/problem/P1439https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338以上两个都是特例，一个是每个元素不重复，一个是每个元素均有5个。正确性说明参考：https://www.luogu.com.cn/article/1bcs9052由于一般情况可能出

https://class.51nod.com/Html/Textbook/Problem.html#problemId=3978&textbookChapterId=724https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337这里一次发车的转移是\([j+1,i]\)，出发时间\(+s\)为\(j+1\)启程返回，偏移\(i-j-1\)就