目录DAG即有向无环图嵌套矩形(不固定起点最长路及其字典序)描述分析解题硬币问题(固定终点的最长路和最短路)描述分析解题小结例题
DAG即有向无环图
这里举出两经典的DAG模型，嵌套矩形和硬币问题
嵌套矩形(不固定起点最长路及其字典序)
描述
有n个矩形，每个矩形可以用 (a,b) 来描述，表示长和宽矩形 X(a,b) 可以嵌套在矩形 Y(c,d) 中，当且仅当 a<c,b<d 或者 b<c,a<d(旋转90度)例如(1,5)可以嵌套在(6,2)内，但不能嵌套在(3,4)中你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内
分析
矩形间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模如果矩形X可以嵌套在Y中，则就从X到Y连一条有向边这个图是无环的，因为一个矩形无法直接或或间接的嵌套在自己的内部也即是说这是以一个DAG因此，我们就是在求DAG上的不固定起点的最长路径
解题
设 d(i) 表示从结点 i 出发的最长路长度
第一步只能走到它的相邻点，那么我们就有：
其中，E为边集，则最终答案是所有的d(i)中的最大值，因此可以用递推或者记忆化搜索计算
第一步，建图，假如用邻接矩阵将矩形间的关系保存在矩阵G中
第二步，编写记忆化搜索程序(调用前先初始化数组为0)
第三步，按字典序输出最佳的方案
假如有这样的 5 个矩形，输入的边长分别是：
建图
先对长和宽来此排序，再按照要求构图， 完成之后，直接记忆化搜索，但由于是不固定起点的，所以不能只从第一个点搜索，而是每个点都要开始搜索
搜索代码：
int dp(int i){ int& ans = d[i];//为表项d[i]声明一个引用ans if(ans > 0) return ans; ans = 1; for(int j=1;j<n;j++) if(G[i][j])ans = max(ans,dp(j)+1); return ans;}
这里使用了一个技巧：为表项d[i]声明一个引用ans，这样，任何对ans的读写实际上都是在对d[i]进行。当d[i]换成d [i] [j] [k] [l] [m] [n] 这样很长的名字时，该技巧的优势就会很明显
然后我们要考虑如何输出字典序最小的方案字典序只是消除并列名次的方法，我们最根本的任务还是求出最长路在把所有的d值计算出来后，选择最大的d[i]所对应的i，而如果有多个i，则选择最小的i，来保证字典序最小接下来选择 d(i) = d(j) +1 且i, j ∈E 的任何一个j，但是为满足字典序最小，需选择最小的j，代码如下
void print_ans(int i){ printf("%d ", i);//第一次i代表最长路的起点节点，以后均代表从该节点开始的路径 for(int j = 1; j <= n; j++) if(G[i][j] && d[i] == d[j]+1)// 如果该图满足可嵌套，且d[i] = d[j] +1 { print_ans(j); //立即输出从节点j开始的路径 break; }}
完整题解代码
#include<stdio.h>#include<string.h>#define MAXN 100+1int n, G[MAXN][MAXN];//存图int x[MAXN], y[MAXN], d[MAXN]; int dp(int i){ int& ans = d[i];//为表项d[i]声明一个引用ans if(ans > 0) return ans; ans = 1; for(int j=1;j<=n;j++) if(G[i][j])ans = max(ans,dp(j)+1); return ans;}void print_ans(int i){ printf("%d ", i);//第一次i代表最长路的起点节点，以后均代表从该节点开始的路径 for(int j = 1; j <= n; j++) if(G[i][j] && d[i] == d[j]+1)// 如果该图满足可嵌套，且d[i] = d[j] +1 { print_ans(j); //立即输出从节点j开始的路径 break; }}int main(){ int t, ans, best; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d", &x[i], &y[i]); if(x[i] > y[i]){ t = x[i]; x[i] = y[i]; y[i] = t; //保证X[]存的是长，Y[]存的是宽 } } memset(G, 0, sizeof(G)); for(int i = 1; i <= n; i++)//建图 for(int j = 1; j <= n; j++) if(x[i] < x[j] && y[i] < y[j]) G[i][j] = 1;//如果第i个矩形的长宽均小于第j个，使图相应的值为1 ans = 0; for(int i = 1; i <= n; i++)//依次递推所有的的节点 if(dp(i) > ans){ best = i;//best是最小字典序 ans = dp(i); } printf("ans=%d\n", ans);//表示最长路长度 print_ans(best); printf("\n"); return 0 ;}
硬币问题(固定终点的最长路和最短路)描述
有 n 种硬币，面值分别为V1, V2······Vn，每种都有无限多给定非负整数 S ，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值
分析
看上去和嵌套矩形问题很不一样，但本题的本质也是DAG上的路径问题将每种面值看作一个节点，设初始状态为S，目标状态为0若当前在状态 i，每使用一个硬币 j，状态便转移到i – Vj
解题
最长路和最短路的求法是类似的，由于终点固定，d(i) 的确切含义变为从结点i出发到结点0的最长路径长度
int dp(int S){ int& ans = d[S]; if(ans >= 0) return ans; ans = 0; for(int i=1;i<=n;i++) if(S >= V[i]) ans = max(ans,dp(S-V[i])+1); return ans;}
回顾一下嵌套矩形的找最长路
int dp(int i){ int& ans = d[i];//为表项d[i]声明一个引用ans if(ans > 0) return ans; ans = 1; for(int j=1;j<n;j++) if(G[i][j])ans = max(ans,dp(j)+1); return ans;}
由于在本题中，路径长度是可以为0的(S本身可以是0)，所以不能再用d=0表示这个d值还没有算过，初始化时也不能再把d全设为0，而要设置为一个负值令初始状态不合法，这里可以用 -1 来表示没有算过，初始化时只需用memset(d,-1,sizeof(d))即可，同时 if(ans>0) 也要改成 if(ans>=0)
但其实，由于结点S不一定真的能到达结点0，所以需要用特殊的d[S]值表示“无法到达”，但在上述代码中，如果S根本无法继续往前走，返回值是0，将被误以为是“已到达终点”的意思
如果把ans初始化为-1呢？但-1代表“还没算过”，所以返回-1相当于放弃了自己的劳动成果
如果把ans初始化为一个很大的整数，从目前来看，它也会被认为是“还没算过”，但至少可以和所有d的初值分开——只需把代码中if(ans>=0)改为if(ans!=-1)即可
int dp(int S){ int& ans = d[S]; if(ans != -1) return ans; ans = -(1<<30); for(int i=1;i<=n;i++){ if(S >= V[i]) ans = max(ans,dp(S-V[i])+1); } return ans;}
另一个常用的解决方法是不用特殊值表示“还没算过”，而用另外一个数组 vis[i] 表示状态 i 是否被访问过
int dp(int S){ if(vis[S]) return d[S]; vis[S] = -1; int& ans = d[S]; ans = -(1<<30); for(int i=1;i<=n;i++) if(S >= V[i]) ans = max(ans,dp(S-V[i])+1); return ans;}
本题要求最小、最大两个值，记忆化搜索就必须写两个，在这种情况下，用递推更加方便(此时需注意递推的顺序)
minv[0] = maxv[0] = 0;for(int i=1;i<=S;i++){ minv[i] = INF;//minv[i]表示最小值 maxv[i] = -INF;//maxv[i]表示最大值}for(int i=1;i<=S;i++){ for(int j=1;j<=n;j++){ if(i >= V[j]){ minv[i] = min(minv[i],minv[i-V[j]]+1); maxv[i] = max(maxv[i],maxv[i-V[j]]+1); } }}printf("%d %d\n",minv[S],maxv[S]);
如何输出字典序最小的方案呢？刚刚介绍的方法仍然适用，如下所示：
void print_ans(int* d,int S){ for(int i=1; i<=n; i++) { if(S>=V[i] && d[S]==d[S-V[i]]+1) { printf("%d ",i); print_ans(d,S-V[i]); break; } }}
上题打印的是路径上的点，而这里打印的是路径上的边
另外一种常用的打印路径的方法：递推时直接用min_coin[S]记录满足min[S]==min[S-V[i]]+1的最小的i，则打印路径时可以省去print_ans()中的循环，并可以方便地把递归改成迭代 (当然，原来的也可以改成迭代，但不那么自然）具体代码如下
for(int i=1;i<=S;i++){ for(int j=1;j<=n;j++){ if(i >= V[j]){ if(min[i]>min[i-V[j]]+1){ min[i] = min[i-V[j]]+1; min_coin[i] = j; } if(max[i]<max[i-V[j]]+1){ max[i] = max[i-V[j]]+1; max_coin[i] = j; } } }}
小结
由于DAG最长 (短）路的特殊性，有两种“对称”的状态定义方式。
状态1：设 d(i) 为从 i 出发的最长路，则
状态2：设 d(i) 为以 i 结束的最长路，则
如果使用状态2，“硬币问题”就变得和“嵌套矩形问题”几乎一样了 (唯一的区别是“嵌套矩形问题”还需要取所有d (i）的最大值）！我们在上面介绍了比较麻烦的状态1，主要是为了展示一些常见技巧和陷阱，实际比赛中不推荐使用。
使用状态2时，有时还会遇到一个问题：状态转移方程可能不好计算，因为在很多时候，可以方便地枚举从某个结点i出发的所有边 (i , j），却不方便“反着”枚举 (j , i）。特别是在有些题目中，这些边具有明显的实际背景，对应的过程不可逆。这时需要用“刷表法”
什么是“刷表法”呢？传统的递推法可以表示成“对于每个状态 i，计算f (i）”，或者称为“填表法”。这需要对于每个状态 i，找到f (i）依赖的所有状态，在某些情况下并不方便。另一种方法是“对于每个状态i，更新f (i）所影响到的状态”，或者称为“刷表法”。对应到DAG最长路的问题中，就相当于按照拓扑序枚举 i，对于每个 i，枚举边 (i , j），然后更新d[j] = max(d[j],d[i]+1)。注意，一般不把这个式子叫做“状态转移方程”，因为它不是一个可以直接计算d[j]的方程，而只是一个更新公式
提示：传统的递推法可以表示成“对于每个状态 i，计算f (i）”，或者称为“填表法”。这需要对于每个状态 i，找到f (i）依赖的所有状态，在某些时候并不方便。另一种方法是“对于每个状态 i，更新f (i）所影响到的状态”，或者称为“刷表法”，有时比填表法方便。但需要注意的是，只有当每个状态所依赖的状态对它的影响相互独立时才能用刷表法
例题
A – A Spy in the Metro
某城市的地铁是线性的，有n（2≤n≤50）个车站，从左到右编号为1～n
有M1辆列车从第1站开始往右开，还有M2辆列车从第n站开始往左开
在时刻0，Mario从第1站出发，目的是在时刻T（0≤T≤200）会见车站n的一个间谍，在车站等车时容易被抓，所以她决定尽量躲在开动的火车上，让在车站等待的总时间尽量短，列车靠站停车时间忽略不计，且Mario身手敏捷，即使两辆方向不同的列车在同一时间靠站，Mario也能完成换乘。
输入：
第1行为n，第2行为T，第3行有n－1个整数t1,t2,…,tn−1（1≤ti≤70），其中ti表示地铁从车站i到i＋1的行驶时间（两个方向一样）第4行为M1（1≤M1≤50），即从第1站出发向右开的列车数目第5行包含M1个整数d1, d2,…, dM1（0≤di≤250，di＜di+1），即各列车的出发时间。第6、7行描述从第n站出发向左开的列车，格式同第4、5行
输出仅包含一行，即最少等待时间。无解输出impossible
分析
时间是单向流逝的，是一个天然的“序”，而影响到决策的只有当前时间和所处的车站可以用 d(i,j) 表示：在时刻i，处于在车站j（编号为1～n）时，最少还需要等待的时间边界条件是d(T,n)=0，其他 d(T,i)（i不等于n）为正无穷
有如下3种决策。
等1分钟。 搭乘往右开的车（如果有） 搭乘往左开的车（如果有）
在程序中定义一个三维数组has_trainhas_train [t] [i] [0] 表示：时刻t，在车站i是否有往右开的火车has_train [t] [i] [1] 表示：时刻t，在车站i是否有往左开的火车
核心代码如下：
for (int i = 1; i <= n-1; i++) dp[T][i] = INF;dp[T][n] = 0;for (int i = T-1; i >= 0; i++){ for (int j = 1; j <=n ; j++) { dp[i][j] = dp[i+1][j] + 1; if(j<n && has_train[i][j][0] && i+t[j] <= T) dp[i][j] = min(dp[i][j],dp[i+t[j][j+1]])//右 if(j>1 && has_train[i][j][1] && i+t[j-1] <= T) dp[i][j] = min(dp[i][j],dp[i+t[j-1][j-1]])//左 }}if(dp[0][1]) puts("impossible");else cout<<dp[0][1]<<endl;
完整ac码
#include <iostream>#include <stdio.h>#include <string.h>using namespace std;const int INF=0x3f3f3f3f;int t[50+10]；int dp[200+10][50+10]；int has_train[200+10][50+10][2];int main(){ int n,T,M1,M2,flag; int casen=0; while(scanf("%d",&n)!=EOF&&n) { memset(has_train,0,sizeof(has_train)); memset(t,0,sizeof(t)); memset(dp,INF,sizeof(dp)); scanf("%d",&T); for(int i=1; i<n; i++) scanf("%d",&t[i]); scanf("%d",&M1); for(int i=1; i<=M1; i++) { scanf("%d",&flag); for(int j=1; j<=n; j++) { flag+=t[j-1]; has_train[flag][j][0]=1; } } scanf("%d",&M2); for(int i=1; i<=M2; i++) { scanf("%d",&flag); for(int j=n; j>=1; j--) { flag+=t[j]; has_train[flag][j][1]=1; } } for(int i=1; i<=n-1; i++) dp[T][i]=INF; dp[T][n]=0; for(int i=T-1; i>=0; i--) for(int j=1; j<=n; j++) { dp[i][j]=dp[i+1][j]+1; if(j<n&&has_train[i][j][0]&&i+t[j]<=T) dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]); if(j>1&&has_train[i][j][1]&&i+t[j-1]<=T) dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); } cout<<"Case Number "<<++casen<<": "; if(dp[0][1]>=INF) puts("impossible"); else cout<<dp[0][1]<<endl; } return 0;}
B – The Tower of Babylon
有n（n<=30)种立方体，每种都有无穷多个要求选一些立方体，摞成一根尽量高的柱子(可以自行选择哪一条作为高)每个立方体的底面长宽分别严格小于它下方立方体的底面长宽
分析
任何时候都只有顶面（底=顶）尺寸会影响到后续决策，美增加一个立方体以后顶面长和宽都必须严格减小，所以这个图也是DAG，可以套用最长路
由于只有三种面，每种立方体只要三个就够了，每输入一个立方体，就可以算作输入了三个不同的立方体(任选一条边作为高)，然后每一个立方体建边，套用DAG上的dp模板
#include <bits/stdc++.h>using namespace std;const int MAXN = 100+10;int n;int H[MAXN];//记录立方体i的高int d[MAXN];//记录以i为起点的最大高度int G[MAXN][MAXN];//记录i是否可以作为j的底，存图int a[3];//3种边长struct Cube{ int x,y;//长和宽} cube[MAXN];void have_edge(int i,int j)//i是否可以作为j的底，可以则连边{ if(cube[i].x>cube[j].x && cube[i].y>cube[j].y) G[i][j]=1;}int dp(int i){ int &ans = d[i]; if(ans > 0) return ans; ans = H[i]; for(int j=0; j<3*n; j++) if(G[i][j]) ans=max(ans,H[i]+dp(j)); return ans;}int main(){ int casen = 0; while(scanf("%d",&n)!=EOF&&n) { int ans=0; memset(d,0,sizeof(d)); memset(G,0,sizeof(G)); for(int i=0; i<n; i++) { scanf("%d %d %d",&a[0],&a[1],&a[2]); sort(a,a+3); cube[3*i].x=a[0],cube[3*i].y=a[1],H[3*i]=a[2]; cube[3*i+1].x=a[0],cube[3*i+1].y=a[2],H[3*i+1]=a[1]; cube[3*i+2].x=a[1],cube[3*i+2].y=a[2],H[3*i+2]=a[0]; } for(int i=0; i<3*n; i++) for(int j=0; j<3*n; j++) have_edge(i,j); for(int i=0; i<3*n; i++) dp(i); for(int i=0 ; i<3*n ; i++) ans=max(ans,d[i]); printf("Case %d: maximum height = %d\n",++casen ,ans); } return 0;}
C – Tour
给定平面n个点(n≤1000)的坐标，按照x递增的顺序给出，保证各点的x都不同且都为正整数
你的任务是设计一条路线，从最左边的点出发，严格向右走到达最右点再严格向左回到最左点，要求除了最左和最右，每个点恰好经过一次，输出最短路径长度
分析
从左到右再回来可以转化成：两个人同事从最左出发，沿着两条不同的路径走，最后到达最右点，并且除了起点和终点都只能有一个人经过，自然想到可以用d(i,j)表示：一个人走到i点，另一个人走到j，还需要走多长距离到达最右点但是我们发现这样状态好像很难转移，比如计算d(i,j)时，我们不知道能不能让i上的1号同学走到i+1，因为从状态里看不出来i+1有没有被j上的2号同学走过，也就是说这个状态定义的难以转移
然后我们可以简单修改一下定义，让d(i,j)表示：1~max[d(i,j)]全部走过，且两个人目前位置是i和j时，还需要走多长距离到达最右点，在这个定义下d(i,j)=d(j,i)，我们再规定始终有i>j，如果j>i了，只需要交换A、B的角色即可，即将i换为j，j换为i，这样，不管是哪个人，下一步只能走到i＋1 , i＋2,…这些点
那么问题又来了，如果走到i＋2，情况变成了“走过1~ i 和 i＋2，但是i＋1没走过”，不合法
那么直接ban了这个路不就可以了，也就是说，d(i,j)只允许其中一个人走到i＋1，而不能走到i＋2, i＋3,…换句话说，状态d(i,j)只能转移到d(i＋1,j)和d(i＋1,i)，这里意思就是：如果第一个人直接走到了i＋2，那么它再也无法走到i＋1了，只能靠第二个人走到i＋1，既然如此，现在就让第二个人走到i＋1
边界是d(n－1,j) = dist(n－1,n)＋dist(j,n)，其中dist(a,b)表示点a和b之间的距离，因为根据定义，所有点都走过了，两个人只需直接走到终点。所求结果是dist(1,2)＋d(2,1)，因为第一步一定是某个人走到了第二个点，根据定义，这就是d(2,1)
#include <bits/stdc++.h>using namespace std;const int MAXN=1000+10;double d[MAXN][MAXN];//第一个走到i第二个人走到j时,还需要走多长距离走完int n;struct point{ int x, y;//坐标}p[MAXN];double dist(int A,int B)//p[A]到p[B]距离，随便怎么实现，这里用hypot(){ int X = p[A].x - p[B].x; int Y = p[A].y - p[B].y; return hypot(X, Y);}double dp(int i, int j)//i>j{ double& ans = d[i][j]; if (ans > 0) return ans; if (i == n - 1) return ans = dist(i, n) + dist(j, n); ans = min(dp(i + 1, j) + dist(i + 1, i), dp(i + 1, i) + dist(i + 1, j)); return ans;}int main(){ while (cin >> n) { memset(d, 0, sizeof(d)); for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y; dp(2, 1); printf("%.2f\n", dist(2, 1) + d[2][1]); } return 0;}
以上就是详解DAG上的DP的详细内容，更多关于DAG上的DP的资料请关注其它相关文章！
绚丽的民族风情，悠久的历史文化。抛开尘世的纷扰，
