DAG上的DP

拓扑图 dp 通常是在拓扑图上求关于 所有路径的某种信息之和 。当然这里
的“和”的运算法则可以是加法或是取 max 和 min 。或者其他定义的运算。
按拓扑序 沿着有向边 转移就可以了。

update:经历了蓝屏未保存后的重写（嘤嘤嘤）

DAG上的dp是动态规划的基础，动态规划的本质就是一个DAG，状态性相当于DAG上的点，

有向边相当于DAG的转移。

许许多多动态规划问题都能建模成DAG来解决。

Q1：矩阵嵌套问题

 

题目描述

 

有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中

当且仅当a<c,b<d或者b<c,a<d u7。例如（1,5）可以嵌套在（6,2）内，

但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，

每一个矩形都可以嵌套在下一个矩形内。如果有多组最优解，输出字典序最小的一组。

 

矩形嵌套是一个典型的“二元关系”，二元关系可以用图来建模。

对于两个矩形,x和y，如果x可以包含y，就从x向y连一条边，代表矩形x可以覆盖矩形y。

这样我们就得到了一个DAG。

题目让我们求最长的矩形序列，显然就是求DAG上的最长路。

设d[i]表示从i节点出发能够到达的最大长度。

状态转移方程：d[i]=max{d[j]+1|(i,j)€E}

记忆化搜索方法：

inline int dfs(int k)
{

int &ans=dp[k];

if(ans>0) return ans;

for(int i=first[k];i;i=edge[i].nxt)

{

int e=edge[i].ed;

ans=max(ans,dfs(e)+1);

}

return ans;
}

 如果有多组最优解找寻字典序最小的方法

对于应该属于最优解的路径上的边(i,j）

总有dp[i]-1=dp[j];

我们通过这个性质寻找路径，寻找过程中依次筛选字典序最小的方案即可。