题目意思：
对于给定的矩形块,宽a,长b，而对于其他的矩形块，如果宽度小于等于a,长度小于等于b,它可以被(a,b)的矩形块覆盖.题目意思就是给n个矩形块,并且已知每个矩形块的宽度和长度..让你求覆盖之后最大的块数..
比如 有3块矩形块
1 1
2 3
3 2
则 (1,1)可被(2,3)覆盖 (1,1)也可被(3,2)覆盖 而(2,3)不能被(3,2) 所以覆盖之后最多只能有2块。。
所以(a1,b1)<=(a2,b2)的情况下,可以被覆盖，故这题应该变成一个二维的最大上升子序列。
故可以考虑对宽度a进行从小到大排列之后.可对长度b求最大上升子序列.
最大上升子序列的求法就是.
考虑b[i]当前这个数 对于i之前的数b[j](0<=j<i) 如果（b[j]<b[i]）则称b[i]可由b[j]到达.
则dp[i]=max(dp[j]+1){(b[j]<b[i]&&0<=j<i).而最大上升子序列个数就为max(dp[i]) (0<=i<n)
代码如下：
#include<iostream>
using namespace std;
int d[10001][2],n,dp[10001];
int cmp(void const *a,void const *b)
{
int *aa=(int *)a,*bb=(int *)b;
if(aa[0]!=bb[0])
return aa[0]-bb[0];
else
return aa[1]-bb[1];
}
int main()
{
while(cin>>n,n)
{
for(int i=0;i<n;i++)
cin>>d[i][0]>>d[i][1];
qsort(d,n,sizeof(d[0]),cmp);
for(int i=0;i<n;i++)
dp[i]=1;
int max=0;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(d[j][1]<=d[i][1]&&dp[i]<dp[j]+1)
dp[i]=dp[j]+1;
}
if(max<dp[i])
max=dp[i];
}
cout<<max<<endl;
}
cout<<'*'<<endl;
}posted on 2009-03-31 15:58
米游 阅读(407)
评论(0) 编辑 收藏 引用 所属分类:
ACM