博文
UVa 103 解题小结——感觉解出来了，但是脑袋好乱
|||
这个题目貌似是我做到现在最复杂的，假设每个box有k维，有n个boxes。如果对于两个boxes，bi，bj，其中一个box的维数排列后，对应位置维数均小于另外一个box，则称其nest于另一个box。问题是对于每个输入的boxes，找出最长的nest串，并输出。如果没解释清楚请参考http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=39 （哎……解释一个问题真的好麻烦）
我的算法基本思路：
1.构造一个数据结构，每个元素代表一个box，每个元素中包含该box 的编号（lab），维数（存放于num数组中），到该元素中的最大长度存放于len，前继编号（pre）和后继编号（next）。详见数据data_type的定义。
2.输入数据，并对每个box维数进行排序，在根据维数对box排序（均为升序）
3.对于每个box与在位于排序后的boxes进行比较，如果发现后面的box的len-1的长度小于前面box的len，则对后面比较的box的len进行更新，其长度为前面box的len+1，并设置后面的这两个box的前继和后继。
4.找出len最大的位置，倒推（根据前继）回起始，并输出。
多个len最大建议选择较小的lab的那个，并在倒推的过程中，每做一次，更新一次前继和后继。听上去没什么用，但是，没有加这个，一直在报错。
5.输出结果
源码：
# include <iostream>
# include <algorithm>
using namespace std;
struct data_type
{
int lab;//该数据编号
int num[10];//每组数据中的sequence
int len;//用于存放到该处的最大长度
int pre;//上一个地址位置，若为999，则表示无前继
int next;//下一个地址的位置，若为999，则表示无后续
}m[30];
int cmp1(const int &a,const int &b)
{
if(a<b)
return 1;
else
return 0;
}
int cmp(const struct data_type &a,const struct data_type &b)
{
for(int i =0;i<10;++i)
{
if(a.num[i]<b.num[i])
return 1;
else if (a.num[i]>b.num[i])
return 0;
if(i==9)
return 0;
}
}
bool nest(int* a,int* b,int dim)
{
for(int i=0;i<dim;++i)
{
if(a[i]>=b[i])
return false;
else if(i==dim-1&&a[i]<b[i])
return true;
else if(i==dim-1&&a[i]==b[i])
return false;
}
}
int longest(struct data_type*a,int n,int&c)
{
int r(0),t(1);
for(int i=0;i<n;++i)
{
if(r<a[i].len||(r==a[i].len&&t>a[i].lab))
{
r=a[i].len;
t=a[i].lab;
c=i;
}
}
for(int i=0;i<r;++i)
{
if(a[c].pre==999)
{
break;
}
t=c;
c=a[c].pre;
a[c].next=t;
}
return r;
}
int main()
{
int n(0),dim(0);
while(cin>>n>>dim)
{
if(n==0)continue;
for(int i =0;i<n;++i)
{
for(int j=0;j<dim;++j)
{
cin>>m[i].num[j];
}
for(int j=dim;j<10;++j)
{
m[i].num[j]=0;
}
m[i].lab=i+1;
m[i].len=1;
m[i].pre=999;
m[i].next=999;
sort(m[i].num,m[i].num+dim,cmp1);
}
sort(m,m+n,cmp);
for(int i=0;i<n-1;++i)
{
bool flag=true;
for(int j=i+1;j<n;++j)
{
if(nest(m[i].num,m[j].num,dim))
{
if(flag)
m[i].next=j;
if(m[i].len>=m[j].len-1)
{
m[j].len=m[i].len+1;
m[j].pre=i;
}
flag=false;
}
}
}
int c(0);
int r=longest(m,n,c);
// for(int i=0;i<n;++i)
// {
// for(int j=0;j<dim;++j)
// {
// cout<<m[i].num[j]<<"t";
// }
// cout<<m[i].lab<<"t"<<m[i].len<<"t";
// cout<<m[i].pre<<"t"<<m[i].next<<endl;
// }
//
// cout<<c<<endl;
cout<<r<<endl;
for(int i=0;i<r-1;++i)
{
cout<<m[c].lab<<" ";
c=m[c].next;
}
cout<<m[c].lab<<endl;
}
}
https://blog.sciencenet.cn/blog-723765-646239.html
上一篇：UVa 102 解题小结——多亏n只是3，要不就跪了
