首页
登录 | 注册

有向无环图DAG上的动态规划

1.嵌套矩形问题:动态规划策略,矩形可嵌套关系是二元有向关系,即求有向图的最长路径问题

2.硬币问题:初始状态为s,末状态为0;


//动态规划策略总是从最后一层向上走,也就是从下一层向上一层返回值,比如说数字三角形向上一层返回下面的最大值,有向无环图的最长路向上返回下面的最长路

//有向无环图的最长路径


动态规划策略三要素:最后一层元素初始化为多少,d[][]保存什么,下一层向上一层返回什么

//DAG的最长路径和打印

//读入一个有向图,最长路径,规定第一个节点为根节点
//动态规划策略:最后节点长度为1,d[i] 保存以i为根结点的最长路大小,下一个节点想上一个节点返回下面节点的长度

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10000;
int n=4;
int G[maxn][maxn];//领接矩阵存图
int d[maxn];
int dp(int i){
    if(d[i]>0)return d[i];
    d[i]=1;
    for(int j=1;j<=n;j++)//遍历i的每一个子节点
        if(G[i][j])d[i]=max(d[i],dp(j)+1);//d[i] 保存i为根结点的最长路
    return d[i];
}
void print(int i){
    printf("%d ",i);
    for(int j=1;j<=n;j++)
        if(G[i][j]&&d[i]==d[j]+1){
            print(j);
            break;//剪枝,减少判断
        }
}
int main(){
    memset(d,0,sizeof(d));
    memset(G,0,sizeof(G));
    int x,y,top;
    cin>>top>>x;
    G[top][x]=1;
    while(cin>>x>>y&&x){
        G[x][y]=1;
    }
    cout<<dp(top)<<" 最长路径"<<endl;
    print(top);
}
 




2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号