【2016.10.7NOIP普及模拟】箱子嵌套

发布于 2019-04-14  10 次阅读


题目描述

考虑一个给出为N维空间“箱子”的尺度问题。当有两个尺度时,箱子(2,3)表示这个箱子长度为2个单位,宽度为3个单位。当有三个尺度时,箱子(4,8,9)表示这个箱子长度是4个单位,宽度是8个单位,高度是9个单位。当它有6个尺度时,也许,它表现的是不易了解的箱子(4,5,6,7,8,9);但是我们能分析这个箱子的特性,例如它的各个尺度。
在这个问题中你将分析许多关于N维空间的箱子,并解决这些箱子的最大的嵌套问题。箱子D =(d1,d2,„,dn),箱子E = (e1,e2,„,en),di和ei都可以重新排列整理,那么当它们重新排列整理后,箱子D所有的尺度都小于箱子E所有的尺度,那么箱子D可以放入箱子E中。
例如,箱子D =(2,6),当D重新排列整理成(6,2),则可放入箱子E =(7,3)中,此时D每个尺度都小于E的相应尺度。如果D经过重新整理后D =(9,7,5,3),则不可以放入箱子E =(10,8,6,2)中,但是F =(9,5,7,1),重新整理后F =(9,7,5,1),即符合F放入E的条件。

输入

输入文件boxes.in中,第一行有两个整数,中间有1个空格,第一个整数为箱子的总
数K,第二个整数为每个箱子的空间维数N。
以下K行,每行表示一个箱子,有N个尺度数据,数据间用一个或数个空格分开。

输出

输出文件Boxes.out仅包含一行一个整数,输出最大箱子嵌套数目。

思路

排序后进行最长不下降子序列,输出最大值就可以了

#include 
#include 
using namespace std;
struct dd 
{ 
    int s[15];
};
dd a[1005];
int f[1005];
int n,m,ans=0;
bool compare(dd a,dd b)
{
    return a.s[1]>b.s[1]; 
}
__attribute__((optimize("O2")))
int ban(int x,int y)
{
    for (int i=1;i<=m;i++)
      if (a[x].s[i]<=a[y].s[i])
      {
          return false;
      }
    return true;
}
__attribute__((optimize("O2")))
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
            scanf("%d",&a[i].s[j]);

        for (int j=1;j<=m-1;j++)
          for (int k=j+1;k<=m;k++)
            if (a[i].s[j]>a[i].s[k])
            {
                int l=a[i].s[j];
                a[i].s[j]=a[i].s[k];
                a[i].s[k]=l;
            }
    }

    sort(a+1,a+n+1,compare);


    for (int i=1;i<=n;i++)
        f[i]=1;
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=i-1;j++)
          if (ban(j,i)&&f[j]+1>f[i])
              f[i]=f[j]+1;
    }
    for (int i=1;i<=n;i++)
        if (f[i]>ans) ans=f[i];
    printf("%d\n",ans);
}
]]>