DAG 模型 stacking boxes 动态规划

题目大意：

给你两个数，一个是盒子的个数，一个是每一个盒子的维数。将一个个盒子互相装起来，让你求最多可以装多少个，要求字典序最小。

解析：这个就是盒子的嵌套，和二维盒子嵌套有点像，只是建图的方法不一样，二维只要判断两个，长和宽即可，而k维需要判断k次，除此之外，其余都是一样的。

方法：前提：dp[i]=max(dp[i],d(j)+1);

第一步，就是建图，map[][]，判断出哪些可以嵌套

第二步：再用一个函数来计算路径长度

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int map1[40][40],gra[40][20];
int dp[40];
int n,k,first;

int creatmap(int x,int y)
{
    if(gra[x][0]<gra[y][0])
    {
        for(int i=1;i<k;i++)
        {
            if(gra[x][i]>=gra[y][i]) return 0;
        }
        return 1;
    }
    else return 0;
}

int d(int x)
{
    int &ans=dp[x];
    if(ans>0) return ans;//记忆化搜索
    ans=1;//因为这个盒子至少有本身，所以是1
    for(int i=0;i<n;i++)
    {
        if(map1[x][i])
        {
            //cout<<x<<"   "<<i<<endl;
            ans=max(ans,d(i)+1);
        }
    }
    return ans;
}

void printf_exa(int x)
{
    if(first==0) {printf("%d",x+1);first=1;}
    else printf(" %d",x+1);
    for(int i=0;i<n;i++)
    {
        if(map1[x][i]&&dp[x]==dp[i]+1)
        {
             printf_exa(i);
             break;
        }
    }
}

int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        memset(map1,0,sizeof(map1));
        memset(dp,0,sizeof(dp));

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<k;j++)
            {
                scanf("%d",&gra[i][j]);
            }
        }
        for(int i=0;i<n;i++) sort(gra[i],gra[i]+k);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i!=j&&creatmap(i,j))
                {
                  //  cout<<i<<" "<<j<<endl;
                    map1[i][j]=1;
                }
            }
        }
        int exa=0,mark;
        first=0;
        for(int i=0;i<n;i++)
        {
            int tmp=d(i);
            if(tmp>exa)
            {
                exa=tmp;
                mark=i;
            }
        }
        cout<<exa<<endl;
        printf_exa(mark);
        printf("
");
    }
    return 0;
}

DAG 模型 stacking boxes 动态规划

相关推荐