NOIP模板代码(C++).doc

动态规划最长公共子串(注意和最长公共子序列区别)两个字符串str1和str2,长度分别为（l1,l2)dpij表示以两个字符串分别以第i和第j个字符结尾所能达到的公共子序列的长度，由于下面涉及到i-1和j-1，那么这个时候我们一般从i=1和j=1开始到i=len1, j 0且j 0 且ch1i-1= ch2j-1; dpij= 0; i 0且j 0 且ch1i-1!= ch2j-1;注意dpi0=0(0=i=max(l1,l2);dp0i=0(0=i=max(l1,l2);最长公共字串要求在原来字符中满足是连续的，最长公共子序列则不要求最长公共子序列：根据最长公共子序列问题的性质，我们可以规定dpij为字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度, 由于下面涉及到i-1和j-1，那么这个时候我们一般从i=1和j=1开始到i=len1, j0且j0且ch1i-1=ch2j-1;dpij=maxdpi-1j,dpij-1;i0且j0且ch1i-1!= ch2j-1;最长上升或下降子序列给定一个序列a1,a2.an;dpi表示以ai结尾的最长上升子序列长度(下降相反）核心代码：注意最长不上升或不下降子序列问题最大子序列的和问题给定一个序列a1,a2.an;求子序列的和最大问题dpi表示以ai结尾的子序列和,max为最大子序列和核心：1 如果输入的数据全部为负数则最大值就是序列中的一个最大值2 如果有正数数塔问题给定一个数组snm构成一个数塔求从最上面走到最低端经过的路径和最大我么采用至底向上的思路求解问题（注意从倒数第二行开始）dpij表示走到第i行第j个的最大值那么就有dpij=maxdpi-1j-1,dpi-1j+sij;最后dp11即为最大值01背包问题有N件物品和一个容量为V的背包。第i件物品的体积是vi，价值是ci。求解将哪些物品装入背包可使价值总和最大。我们知道对于没一件物品我们有两种可能就是放与不放dpij表示第i件物品放入容量为j的背包所得的最大价值dpij=maxdpi-1j-vi+ci,dpi-1j;这里我们从j=V倒推回来的话可以优化成dpj=maxdpj,dpj-vi+ci;核心代码：dpv即为最大的价值完全背包问题有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是vi，价值是i。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这时候对于没见物品就不是放与不放的问题了，而是放0件1件.这时候我们可以像01背包一样dpij表示容量为的背包第i件物品是否要再一次放入所以我们要从0-顺序循环dpij=maxdpi-1j-vi+ci,dpi-1j(注意这里和01背包一样但是求解的过程不同）优化后：dpj=maxdpj,dpj-vi+ci;核心代码：注意这列求出的dpv是最大的因为一直叠加多重背包问题有N种物品和一个容量为V的背包。第i种物品最多有ni件可用，每件费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。因为对于第i种物品有ni+1种策略：取0件，取1件取ni件。重点：令dpij表示前i种物品恰放入一个容量为j的背包的最大价值状态转移方程：dpij=maxdpi-1v-k*vi+k*ci|0=k0,无论ai为何值，有dpi=dpi-1+ai; 2如果dpi-10) dpi=ai(dpi-1=0)最大m子段和在限制条件增加一维时,可以将状态也相应的增加一维,来进行状态转移以dpij表示以第i个元素为结尾,使用j个子段所能达到的最大值(这一维的状态,正是对应了新的限制条件!)这样就很容易写出状态转移方程:dpij=maxdpi-1j+ai,dpi-kj-1+ai(j-1=kn-m+j)1 dpi-1j+ai(把第i个元素包含在最后一个子段内)2 dpi-kj-1+ai,j-1=kn-m+j(第i个元素单独为一子串)矩阵连乘问题描述：给定一序列的矩阵要求找到一种矩阵连乘的顺序，使得连乘的次数最少思路：建立递推表达式，利用动态规划的方式(mij表示第i个矩阵至第j个矩阵这段的最优解,还有对于两个矩阵M(i,j)*S(j,k)则需要i*j*k次乘法)1显然如果i=j，则mij这段中就一个矩阵，需要计算的次数为0；2如果i j，则mij=minmik+mk+1j+pi-1*pk*pj,其中k,在i与j之间游荡，所以i=kj;3因为你要保证在计算mij查找mik和mk+1j的时候，mik和mk+1j已经计算出来了所以有动态转移方程：mij=0,i=jmij=minmik+mk+1j+pi-1*pk*pj,i!=j;m1n即为最终求解白书上面写道：记忆化搜索固然没有问题，但如果要写成递推，无论按照i还是j的递增或递减均不争确。正确的方法是按照j-i递增的顺序递推，因为长区间的值依赖于短区间的值模板：int dpMAXNMAXN;/存储最小的就算次数int sMAXNMAXN;/存储断点，用在输出上面核心代码：输出：区间DP区间动态规划问题一般都是考虑，对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合，求合并后的最优值。1 设Fi,j（1=i=j=n）表示区间i,j内的数字相加的最小代价 2 最小区间Fi,i=0（一个数字无法合并，代价为0） 3 每次用变量k（i=k=j-1）将区间分为i,k和k+1,j两段 4区间DP模板，代码数论最大公约数：扩展欧几里得：最小公倍数：快速幂：筛素数1：筛素数2：图论链式前向星：结构：初始化：拓扑排序（邻接矩阵）：拓扑排序（链式前向星）：Dijkstra（邻接矩阵）：Dijkstra（链式前向星）：SPFA：Floyd：Floyd最小环：Kruskal：Tarjan求强连通分量：调用：问：要将一个非强连通图变成强连通图，需要添加多少条边？二分图最大匹配：数据结构并查集线段树建树更新查询树状数组建树更新特殊应用：找整个数列的第K小数常用库函数字符串转换函数：字符串转换为长整数：atol字符串转换为浮点数：strtod字符串转换为长整数：strtol字符串转换为无符号长整型：strtoul字符串连接：按长度连接字符串字符串大小比较（按字符比较ASCII码）原型：extern int strcmp(const char *s1,const char * s2);所在头文件：string.h功能：比较字符串s1和s2。一般形式：strcmp(字符串1，字符串2)说明：当s1s2时，返回正