NOIP的DP总结之经典模型.docxVIP

DP经典模型（母题总结）contentL_S免费馅饼矩阵dp双塔DP石子合并选课数字三角形打砖块子矩阵最大子段和方格取数Hanoi数的划分逆序对最短回文串硬币问题形成非降序列的最少合并次数L_S问题LIS LCS LCIS话说LCS有O（n*m）的算法，LIS也有O（n*m）的算法；XX日，LIS被栈和二分优化了，复杂度变为了nlogn，q[1]:=a[1]; top:=1; for i:=2 to n do begin if a[i]q[top] then begin inc(top); q[top]:=a[i]; end else begin l:=1;r:=top; while lr do begin mid:=(l+r)div 2; if q[mid]a[i] then r:=mid else l:=mid+1; end; q[l]:=a[i]; end; end;于是n排列的LCS也被优化了，也达到了nlogn.nlogn的LCS：设有序列A，B。记序列A中各个元素在B?中的位置，用序列C存，求C的LIS即可。LCS与LIS结合，于是有了LCIS，LCIS有n*m的算法。代码如下：for i:=1 to n do begin t:=0; for j:=1 to n do begin if a[i]b[j] then if f[j]t thent:=f[j]; if a[i]=b[j] then if t+1f[j] thenf[j]:=t+1; if f[j]ans then ans:=f[j]; end; end;解释可以参考资料里的某文档或百度文库。变式训练：导弹拦截，合唱队型，船，交错匹配，最高线段覆盖，最大子段和*1*一般的最大子段和：F[i]:=max{f[i-1]+a[i],a[i]}Ans:=max{f[i]}*2*元素不可重复计算的最大子段和（cwx吃面包）：S[a]表示a到b不重复计算的子段和，F[a]表示s[a]出现过的最大值。Pre[k]表示元素k上一次出现过的地方For b:=1 to n do Begin For a:=pre[w[b]]+1 to b do BeginS[a]:=s[a]+w[b];F[a]:=max(f[a],s[a]); End; End;Ans:=max{f[a]}*3*最大M子段和F[i,j]表示前i个数，i 属于第j子段时的最大值。 G[I,j]表示前i个数，分了j个子段时的最大值。 F[I,j]:=max{f[i-1,j],g[i-1,j-1]}+a[i]; G[I,j]:=max{g[i-1,j],f[i,j]}.空间可以优化。反思：状态的巧妙设计，互补设计。M=2时另有做法： 顺做一次最大子段和x[i]，到做一次最大子段和y[i]，Ans:=max{x[i]+y[i+1]}.枚举断点法，很实用！*4*长度限制的最大子段和可用单调队列优化。最大子段和最大m子段和（——必做！）（n=106 ,m=50,允许空间O(n)） 算法1: F[i,j]表示前i个数，i 属于第j子段时的最大值。 F[i,j]:=max{f[i-1,j],f[k,j-1]}+a[i].(1=ki) 过不了！算法2: G[I,j]表示前i个数，分了j个子段时的最大值。 F[I,j]:=max{f[i-1,j],g[i-1,j-1]}+a[i]; G[I,j]:=max{g[i-1,j],f[i,j]}. 过不了！ 算法3: 根据分析g(i,j)=max{g(i-1,j),f(i,j)}发现，g要么和前一个状态g(i-1,j)相同，要么和此时所得的数f(i,j)相同。同样的，f(i,j)=max{f(i-1,j)+a[i],g(i-1,j-1)+a[i]}中，f-a[i]要么和前一个状态相同，要么和前一个最优解g相同。所以，我们可以用一维数组来代替二维数组。F[j]:=max{f[j],g[j-1]} +a[i]; G[j]:=max{f[j],g[j]}.成功AC！最大不重复子段和：cwx吃面包问题。平方做法。子矩阵问题*1*最大01子矩阵枚举下边界，利用悬线的观点，然后有两种做法：路径压缩法和两次单调队列法。其实还可以将不要的一方赋值为-oo，从而转化为*3*最大子矩阵问题。*2*另外，最大01子正方形： f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1; ans:=maxvalue(f);?*3*最大子矩阵枚举上下边界，化二维为一维（最大子段和问题）。变式：*1*找一个矩阵，使得其中的1的个数减去0的个数最大，输出最大值。方法：将0变为-1，问题转化成最大子矩阵*2*AHOI 2007宝库通道*3*最大面积【题目描述】已知一个大矩形的长和高 l