题目描述

考虑一个给出为N维空间“箱子”的尺度问题。当有两个尺度时，箱子（2，3）表示这个箱子长度为2个单位，宽度为3个单位。当有三个尺度时，箱子（4，8，9）表示这个箱子长度是４个单位，宽度是8个单位，高度是9个单位。当它有6个尺度时，也许，它表现的是不易了解的箱子（4，5，6，7，8，9）；但是我们能分析这个箱子的特性，例如它的各个尺度。
在这个问题中你将分析许多关于Ｎ维空间的箱子，并解决这些箱子的最大的嵌套问题。箱子Ｄ =（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);
}