USACO2007 The Bale Tower /// DFS oj21160

题目大意：

给出N个捆包，每个捆包有相应的长度和宽度，要求堆叠捆包，使下方的捆包长宽永远大于上方的捆包的长宽。

Input

Multiple test case. For each case:

* Line 1: A single integer, N

* Lines 2..N+1: Each line describes a bale with two space-separated integers, respectively the width and breadth

Output

For each case, output one line: The height of the tallest possible tower that can legally be built from the bales.

Sample Input

6
6 9
10 12
9 11
8 10
7 8
5 3

Sample Output

方法一

先结构体sort()对长排序长相等时对宽排序，再枚举各个宽为底，算出所有可能结果，再求出最大结果

#include <bits/stdc++.h>

using namespace std;

int n,ans;

struct BALE

{

    int x,y;

}bale[];

bool cmp(struct BALE q,struct BALE p)

{

    if(q.x==p.x) return q.y<p.x;

    return q.x>p.x;

}

void cnt(int i,int sum)

{

    ans=max(ans,sum);

    if(sum==n) return;

    for(int j=i+;j<n;j++)

        if(bale[i].y>=bale[j].y)

        {

            cnt(j,sum+);

            if(sum==n) return;

        }

}

int main()

{

    while(~scanf("%d",&n))

    {

        ans=;

        for(int i=;i<n;i++)

            scanf("%d%d",&bale[i].x,&bale[i].y);

        sort(bale,bale+n,cmp);

        for(int i=;i<n;i++)

        {

            cnt(i,);

            //printf("%d\n",cnt(i));

        }

        printf("%d\n",ans);

    }

    return ;

}

—— 01.28更 ——

OJ测试数据更新了之后这份代码狗带了因为相同的情况是不能考虑的

如：

9 3

8 4

答案应为 1

按方法二补

#include <bits/stdc++.h>

using namespace std;

int n,ans,flag[];

struct BALE

{

    int x,y;

}bale[];

void DFS(int i,int sum)

{

    ans=max(sum,ans);

    if(sum==n) return;

    for(int j=;j<=n;j++)

    {

        if(bale[i].x>bale[j].x&&bale[i].y>bale[j].y&&!flag[j])

        {

            flag[j]=;

            DFS(j,sum+);

            flag[j]=;

        }

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

        ans=;

        for(int i=;i<=n;i++)

            scanf("%d%d",&bale[i].x,&bale[i].y);

        for(int i=;i<=n;i++)

        {

            memset(flag,,sizeof(flag));

            flag[i]=;

            DFS(i,);

        }

        printf("%d\n",ans);

    }

    return ;

}

————————

方法二

DFS深搜（偷下LXH的代码）

还是需要添加标记

巴特西

USACO2007 The Bale Tower /// DFS oj21160

最新文章

热门文章