搜索
区间DP•区间DP的定义：–区间动态规划一般都是考虑对于每段区间，他们的最优值都是由几段更小的区间直至一个元素组成的区间，枚举他们的组合，求合并后的最优值。=9304&pid=1000•Poj2955Brackets•题意:求一个字符串的最大的括号匹配长度•if(s[j]=='['&&s[k]==']'||s[j]=='('&&s[k]==')')dp[j][k]=dp[j+1][k-1]+2;•for(z=j;zk;z++)dp[j][k]=max(dp[j][k],dp[j][z]+dp[z+1][k]);•具体代码概率DP•概率DP主要用于求解期望、概率等题目=9304&pid=1001•zoj3822Domination•题意:在一个n*m的棋盘上放棋子，一个棋子可覆盖一行一列，若n行m列全被覆盖则停止放棋子，求棋子的期望•期望：离散随机变量的一切可能值与其对应的概率P的乘积之和•dp[i][j][k]表示放了i个棋子覆盖了j行k列•已知dp[0][0][0]=1,求dp[1~n*m][n][m]1.再放一个棋子，行列都不增加•dp[i+1][j][k]+=dp[i][j][k]*(j*k-i)*1.0/(m*n-i);2.只增加一行•dp[i+1][j+1][k]+=dp[i][j][k]*(n-j)*k*1.0/(m*n-i);3.只增加一列dp[i+1][j][k+1]+=dp[i][j][k]*(m-k)*j*1.0/(m*n-i);4.增加了一行一列dp[i+1][j+1][k+1]+=dp[i][j][k]*((m-k)*(n-j))*1.0/(m*n-i);•具体代码树形DP•定义：树型DP就是在“树”的数据结构上的动态规划，平时做的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向即向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向。•根-叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的问题。•叶-根：即根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多。=1003&cid=25386•Anniversaryparty•题意:n个人形成一个关系树，每个节点代表一个人，节点的跟表示这个人的唯一的直接上司。每个人有一个欢乐值，要求选取一部分人出来，使得每2个人之间不能有直接的上下级的关系，并且使欢乐值最大。•dp[i][0]表示不选i号节点能得到的最大欢乐值•dp[i][1]表示选i号节点能得到的最大欢乐值•dp[i][0]+=max(dp[j][0],dp[j][1]);•dp[i][1]+=dp[j][0];(j表示i的子节点)•dp[i][1]=w;•具体代码插头DPHDU1693•题意：在n*m(1=N,M=11)的矩阵中，有些格子有树，没有树的格子不能到达，找若干条回路，吃完所有的树，求有多少种方法。初步分析•问题特点：•数据规模小m,n≤12搜索?O((mn)!)状态压缩!√•棋盘模型划分阶段：从上到下，从左到右逐格递推基本概念：插头，轮廓线基本概念•插头一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子连接一条线．•轮廓线已决策格子和未决策格子的分界线轮廓线上方与其相连的最多有m+1个插头，包括m个下插头和1个右插头．初步分析•问题特点：•数据规模小•棋盘模型每个插头是否存在确立状态•设f(i,j,S)表示转移完(i,j)，轮廓线上从左到右m+1个插头状态为S的方案总数．•如何表示S（m+1位的二进制数）11101•无插头标记0，有插头标记1f(3,2,{1,1,1,0,1})状态的转移•每次转移相当于轮廓线上当前决策格子的左插头改成下插头，上插头改成右插头的状态．状态的转移•这题中显然一个格子中要么有两个插头（经过这个格子），要么没有插头（不经过这个格子），因为不可能分叉走，每个格子走一次。状态的转移•1、当前格子有树时，•（1）这个状态表示（101111），当前决策格子是第二行第三个格子，显然它已经有了两个插头，也就是有1条线穿过它，所以不用再加插头了。状态的转移•（2）这个状态是（100111）和（101011）,当前决策格子是第二行第三个格子,显然有一个插头了，再添加一个即可，那么就有两个选择，要么向下，要么向右，就要有两个转移。状态的转移•（3）这个状态是（100011）,当前决策格子是第二行第三个格子,显然之前没有有一个插头了，只能添加两个，或者不添加，不添加，就肯定不经过这个格子，显然只能这个格子是不可行的。状态的转移•2、当前格子没树时，•当前格子不能有插头•详细转移方程看代码•