DAG上的动态规划「一」

有向无环图DAG
算法中有时称有向无环图为DAG ( Directed Acyclic Graph)。所谓有向无环图是指：任意一条边有方向，且不存在环路的图。

有向无环图上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径计数问题

DAG模型(不固定起点的最长路径)

嵌套矩形问题

题意：

• 有个矩形，每个矩形可以用来描述，表示长和宽
  矩形 可以嵌套在矩形 中，当且仅当 或者 (旋转90度)
  例如可以嵌套在内，但不能嵌套在中
  你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。如果有多解，矩形编号的字典序应尽量小

分析：

• 矩形间的嵌套问题是一个典型的二元关系，二元关系可以用图来建模。如果矩形可以嵌套在矩形里，就有一条有向边。这个有向图是无环的，因为一个矩形无法直接或间接的嵌套在自己内部。DAG模型就构造出来了，原问题的解就是有向图的最长路径

#include<bits/stdc++.h>
using namespace std;
int mp[110][110];
int x[110],y[110];
int dp[110];
int n;
int nxt[110];
int solve(int i)
{
    if(dp[i]>0)
    {
        return dp[i];
    }
    dp[i]=1;
    for(int j=1;j<=n;j++)
    {
        if(mp[i][j]!=0)
        {
           int tep=solve(j)+1;
           if(tep>dp[i])
           {
               dp[i]=tep;
               nxt[i]=j;
           }
        }
    }
    return dp[i];
}
void print(int i)
{
    stack<int> s;
    while(i!=-1)
    {
        s.push(i);
        i=nxt[i];
    }
    while(!s.empty( ))
    {
        cout<<s.top( )<<" ";
        s.pop( );
    }
    cout<<endl;
}
int main( )
{
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            if(x[i]<y[i])
            {
                swap(x[i],y[i]);
            }
        }
        memset(mp,0,sizeof(mp));
        memset(dp,0,sizeof(dp));
        memset(nxt,-1,sizeof(nxt));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(x[i]>x[j]&&y[i]>y[j])
                {
                    mp[i][j]=1;
                }
            }
        }
        int ans=-1;
        int flag;
        for(int i=1;i<=n;i++)
        {
            if(solve(i)>ans)
            {
                ans=solve(i);
                flag=i;
            }
        }
        cout<<ans<<endl;
        print(flag);
    }
    return 0;
}

Monkey and Banana

题意：

有种立方体，每种都有无穷个。要求是选一些立方体摞成一根尽量高的柱子(可自行选择那一条边作为高)，使得每个立方体底面长宽分别严格小于它下方立方体发底面长宽。(类似于矩形嵌套）
典型的DAG模型

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int a,b,c;
}edge[300];
int cnt;
int dp[300];
void add(int a,int b,int c)
{
    edge[cnt].a=a;
    edge[cnt].b=b;
    edge[cnt].c=c;
    cnt++;
}
int solve(int i)
{
    if(dp[i]>0)
    {
        return dp[i];
    }
    dp[i]=edge[i].c;
    for(int j=0;j<cnt;j++)
    {
        if((edge[j].a<edge[i].a)&&(edge[j].b<edge[i].b))
        {
            dp[i]=max(dp[i],solve(j)+edge[i].c);
        }
    }
    return dp[i];
}
int main( )
{
    int n,x,y,w;
    int k=0;
    while(~scanf("%d",&n)&&n)
    {
        cnt=0;
        k++;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            add(x,y,w);
            add(x,w,y);
            add(y,x,w);
            add(y,w,x);
            add(w,x,y);
            add(w,y,x);
        }
        //cout<<cnt<<endl;
        memset(dp,0,sizeof(dp));
        int ans=-1;
        for(int i=0;i<cnt;i++)
        {
            ans=max(solve(i),ans);
        }
        // for(int i=0;i<cnt;i++)
        // {
        //     cout<<dp[i]<<" ";
        // }
        // cout<<endl;
        printf("Case %d: maximum height = %d\n",k,ans);
    }
    return 0;
}

Coolest Ski Route

#include<bits/stdc++.h>
using namespace std;
const int M=5010;
int head[M],cnt;
struct node
{
    int v,w,nxt;
} edge[M];
int dis[M];
void add(int x,int y,int w)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    edge[cnt].w=w;
    head[x]=cnt;
}
int maix;
int dfs(int x)
{
    int &ans=dis[x];
    if(ans>0)
    {
        return ans;
    }
    ans=0;
    for(int i=head[x]; i!=-1; i=edge[i].nxt)
    {
        int v=edge[i].v;
        ans=max(ans,dfs(v)+edge[i].w);
    }
    return ans;
}
int main( )
{
    int n,m,x,y,w;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        for(int i=1; i<=n; i++)
        {
            head[i]=-1;
            dis[i]=0;
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            add(x,y,w);
        }
        maix=-1;
        for(int i=1; i<=n; i++)
        {
            if(dis[i]==0)
            {
                maix=max(maix,dfs(i));
            }
           
        }
        printf("%d\n",maix);
    }
    return 0;
}