首页 > 代码库 > DAG模型
DAG模型
数字三角形：
1、递归计算
int solve(int i,int j) { return a[i][j] +(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));}
2、记忆化搜索，不用指明计算顺序，并且保证每个状态只计算一次
int solve(int i,int j) { if(d[i][j]>=0) return d[i][j]; return d[i][j] = a[i][j] +(i==n?0:max(solve(i+1,j),solve(i+1,j+1)));}
3、递推计算
for(int j=1;j<=n;j++) d[n][j] = a[n][j];for(int i=n-1;i>=1;i--) { for(int j=1;j<=i;j++) { d[i][j] = a[i][j] + max(d[i+1][j],d[i+1][j+1]); }}
刘汝佳紫书P262
嵌套矩形问题：
典型的二元关系，用图来建模，要是x可以嵌套在y里面，就x->y连线，这个图是有向无环图，有向可以理解，无环的意思就是说，一个矩形不可能直接或者间接的把自己嵌套起来。
问题： 求最多嵌套多少？
就是在这个图上求一个最长路
同数字三角形那样，d(i)表示从节点I出发的最长路的长度
那么d(i) = max{(d[j]+1)|(i,j)ŒE};最后遍历一遍d(i);
#include <bits/stdc++.h>using namespace std;#define maxn 10000int G[maxn][maxn];int dp[maxn];int n; //n个节点//DAGint DAG(int i) { int &ans = dp[i]; if(ans>0) return ans; ans = 1; for(int j=1;j<=n;j++) { if(G[i][j]) ans = max(ans,DAG(j)+1); } return ans;}void print_ans(int i) { printf("%d ",i); for(int i=1;i<=n;i++) { if(G[i][j]&&d[i]==d[j]+1) { print_ans(j); break; } }}int main(){ memset(dp,0,sizeof(dp)); //建图 for(int i=1;i<=n;i++) DAG(i); int ans = -1; int f = -1; for(int i=1;i<=n;i++) { if(ans<dp[i]) { ans = dp[i]; f = i; } } print_ans(i); return 0;}
硬币问题：(固定了终点，状态起点是S，状态终点是0)
最长路，最短路。
代码编译不能过，很多函数写同名了，主要记录思想。
以 i 出发的最长路：d(i) = max(d(j)+1|(i,j)<E)
以 i 结束的最长路：d(i) = max(d(j)+1|(j,i)<E)
推荐方案二。
对于方案一，代码细节难度有一点高。
第一： S = 0，本身是可以的，所以dp[N]初始化-1；然后遇到没有计算的，ans = 0;是错误的，原因：节点S不一定到达0状态，但是返回值却是0,而0却可以是别的含义，就是S = 0，不用拿硬币。所以ans = -INF;
用vis数组会方便很多，思路清晰，保证每个状态只访问一次。而且不用担心特殊值之间的冲突了。
然后，求最大，最小两个值，记忆化搜索要写两个。
这时可以递推。注意递推顺序。得到minv,maxv数组，这是可以像记忆化搜索那样搜索路径。
minv[S] ==minv[S-v[j]] + 1;printf("%d ",j);
但是有更好的方案：
就是找到局部最优方案时记录路径。
min_coin[i] = j;max_coin[i] = j;
然后递归打印，这样就不用循环遍历了
void print_ans(int *min_coin,int S) { while(S) { printf("%d ",min_coin[S]); S-=v[min_coin[S]]; }}
下面是全部代码：
//固定终点的最长路和最短路#include <bits/stdc++.h>using namespace std;#define N 10000#define INF 0x3f3f3f3fconst int v[] = {0,1,2,5,10,20,50,100};int n; //硬币总数int S; //总钱数int dp[N];bool vis[N];int dp(int S) { int & ans = dp[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;}//dp方案二,利用vis数组标记状态int dp(int S) { if(vis[S]) return dp[S]; vis[S] = 1; int & ans = dp[S]; ans = -(1<<30); for(int i=1;i<=n;i++) { if(S>=v[i]) ans = max(ans,dp(S-v[i])+1); }}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; } }}//改进的print_ans()void print_ans(int &min_coin,int S) { while(S) { printf("%d ",min_coin[S]); S-=v[min_coin[S]]; }}int main(){ scanf("%d",&S); memset(vis,0,sizeof(vis)); memset(dp,-1,sizeof(dp)); int ans = dp(S); if(ans!=(1<<30)) printf("OK"); int minv[N] = {0}; int maxv[N] = {0}; minv[0] = maxv[0] = 0; for(int i= 1;i<=S;i++) { minv[i] = INF; maxv[i] = -INF; } 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]); print_ans(minv,S); print_ans(maxv,S); //空间换时间 int min_coin[N]; int max_coin[N]; for(int i=1;i<=S;i++) { for(int j=1;j<=n;j++) { if(i>=v[j]) { if(minv[i]>minv[i-v[j]]+1) { minv[i] = minv[i-v[j]]+1; min_coin[i] = j; } if(maxv[i]<maxv[i-v[j]]+1) { maxv[i] = maxv[i-v[j]] + 1; max_coin[i] = j; } } } } return 0;}
DAG模型
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。