noip中的dp基本类型

《noip中的dp基本类型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOIP中的DP基本类型恩。。贪心我倒没有总结，我只有DP的--

2、我把这些DP总结给你吧：NOIP中的DP基本类型1、背包模型包括0-1背包、无限背包、有限背包、有价值背包、小数背包（贪心即可)等，是极为经典的模型，其转化与优化也是很重要的。2、最长非降子序列模型改版：渡河问题、合唱队型等3、最大子段和模型改版：K大子段和、最佳游览，最大子矩阵和等。4、LCS模型改版：回文字串、多串的LCS等5、括号序列模型改版：关灯问题（TSOJ）、charexp（TSOJ）、最大算式等，核心思想在于以串的长度为阶段。6、递推模型这类题是属于徘徊在DP与递

3、归之间得一类题，本质是类似于记忆化搜索的一种填表，有很强的数学味。7、线段覆盖问题改版：Tom的烦恼（TOJ）等。经常利用到离散化等技巧辅助。8、单词划分模型和LCS基本上构成了字符串DP的主要类型。改版：奇怪的门（TOJ）等。9、股票模型这是DP优化的经典模型。改版有换外汇等。10、连续段划分模型即要求把数列划分成k个连续段，使每段和的最大值最小。改版有任务调度等。11、游戏模型这类题的阶段（一般是时间）和决策（一般就是游戏目标）很清楚，因此比较容易想到。改版：免费馅饼（NOI98）、HelpJimmy（CEOI2000）、瑰丽华尔兹（NO

4、I2005，优化需要多费功夫）。还有就是基础方程式：题目大多数大家可以Google到，且不少是NOI和Vijos原题~~字数关系，就不贴每题的题目了~~1.资源问题1-----机器分配问题f[i,j]:=max(f[i-1,k]+w[i,j-k]);2.资源问题2------01背包问题f[i,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);3.线性动态规划1-----朴素最长非降子序列f[i]:=max{f[j]+1}4.剖分问题1-----石子合并f[i,j]:=min(f[i,k]+f[k+1,j]+sum[i

5、,j]);5.剖分问题2-----多边形剖分f[i,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);6.剖分问题3------乘积最大f[i,j]:=max(f[k,j-1]*mult[k,i]);7.资源问题3-----系统可靠性(完全背包)f[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]};8.贪心的动态规划1-----快餐问题f[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2)divp3};9.贪心的动态规划2-----过河f[i]=m

6、in{{f(i-k)}(notstone[i]){f(i-k)}+1}(stone[i]);+贪心压缩状态10.剖分问题4-----多边形-讨论的动态规划F[i,j]:=max{正正f[I,k]*f[k+1,j];负负g[I,k]*f[k+1,j];正负g[I,k]*f[k+1,j];负正f[I,k]*g[k+1,j];}g为min11.树型动态规划1-----加分二叉树(从两侧到根结点模型)F[i,j]:=max{f[i,k-1]*f[k+1,j]+c[k]};12.树型动态规划2-----选课(多叉树转二叉树,自顶向下模型)f[i,j]表

7、示以i为根节点选j门功课得到的最大学分f[i,j]:=max{f[t[i].l,k]+f[t[i].r,j-k-1]+c[i]};13.计数问题1-----砝码称重f[f[0]+1]=f[j]+k*w[j];(1<=i<=n;1<=j<=f[0];1<=k<=a[i];)14.递推天地1------核电站问题f[-1]:=1;f[0]:=1;f[i]:=2*f[i-1]-f[i-1-m];15.递推天地2------数的划分f[i,j]:=f[i-j,j]+f[i-1,j-1];16.最大子矩阵1-----一最大01子矩阵f[i,j]:=mi

8、n(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;ans:=maxvalue(f);17.判定性问题1-----能否被4整除g[1,0]:=true;g[1,1]:=false;g[1,2]:=false;g[1,3]:=false;g[i,j]:=g[i-1,k]and((k+a[i,p])mod4=j)18.判定性问题2-----能否被k整除f[i,j±n[i]modk]:=f[i-1,j];-k<=j<=k;1<=i<=n20.线型动态规划2-----方块消除游戏f[i,i-1,0]:=0f[i,j,k]:=max{f

9、[i,j-1,0]+sqr(len(j)+k),//dof[i,p,k+len[j]]+f[p+1,j-1,0]//notdo};ans:=f[1,m,0];21.