題目意思：
對(duì)于給定的矩形塊,寬a,長b，而對(duì)于其他的矩形塊，如果寬度小于等于a,長度小于等于b,它可以被(a,b)的矩形塊覆蓋.題目意思就是給n個(gè)矩形塊,并且已知每個(gè)矩形塊的寬度和長度..讓你求覆蓋之后最大的塊數(shù)..
比如 有3塊矩形塊
1 1
2 3
3 2
則 (1,1)可被(2,3)覆蓋 (1,1)也可被(3,2)覆蓋 而(2,3)不能被(3,2) 所以覆蓋之后最多只能有2塊。。
所以(a1,b1)<=(a2,b2)的情況下,可以被覆蓋，故這題應(yīng)該變成一個(gè)二維的最大上升子序列。
故可以考慮對(duì)寬度a進(jìn)行從小到大排列之后.可對(duì)長度b求最大上升子序列.
最大上升子序列的求法就是.
考慮b[i]當(dāng)前這個(gè)數(shù) 對(duì)于i之前的數(shù)b[j](0<=j<i) 如果（b[j]<b[i]）則稱b[i]可由b[j]到達(dá).
則dp[i]=max(dp[j]+1){(b[j]<b[i]&&0<=j<i).而最大上升子序列個(gè)數(shù)就為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
米游 閱讀(449)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM