Rectangles
時間限制： 1000 ms | 記憶體限制： 65535 KB 難度： 2
- 描述
-
Given N (4 <= N <= 100) rectangles and the lengths of their sides ( integers in the range 1..1,000), write a program that finds the maximum K for which there is a sequence of K of the given rectangles that can "nest", (i.e., some sequence P1, P2, ..., Pk, such that P1 can completely fit into P2, P2 can completely fit into P3, etc.).
A rectangle fits inside another rectangle if one of its sides is strictly smaller than the other rectangle's and the remaining side is no larger. If two rectangles are identical they are considered not to fit into each other. For example, a 2*1 rectangle fits in a 2*2 rectangle, but not in another 2*1 rectangle.
The list can be created from rectangles in any order and in either orientation.
- 輸入
-
The first line of input gives a single integer, 1 ≤ T ≤10, the number of test cases. Then follow, for each test case：
* Line 1: a integer N , Given the number ofrectangles N<=100
* Lines 2..N+1: Each line contains two space-separated integers X Y, the sides of the respective rectangle. 1<= X , Y<=5000
輸出 - Output for each test case , a single line with a integer K , the length of the longest sequence of fitting rectangles. 樣例輸入
-
148 1416 2829 1214 8 樣例輸出 -
2 來源 - 第七屆河南省程式設計大賽 上傳者
- 516108736
分析：
我真是WA了無數次啊，沒讀懂題意，是以說題意還是很重要得，我認為的兩個坑點：
（1）“A rectangle fits inside another rectangle if one of its sides is strictly smaller than the other rectangle's and the remaining side is no larger. ”這裡的邊是任意的意思，而不是長對應長，寬對應寬，隻要有第一個長方形的一邊小于第二個長方形的一邊，第一個長方形的另一邊小于等于第二個長方形的另一邊就行了，不用非要長對應長，寬對應寬。
（2）“The list can be created from rectangles in any order and in either orientation.”這句話可以說是非常重要了，可以以任何次序和任何方向，就是說，可以向前，也可以向後（把題目了解成，正序一遍，逆序一遍了，WA了幾次……）。
比如：
1 2
3 5
2 4
1 1
輸出：4
通過上邊的例子可以知道“以任何次序任何方向”是什麼意思了吧……
總結：這種可以方向改變的，我們不如輸入的時候，第一個值存小的，第二個值存大的，給它排序，讓第一個數小的在前，若同樣大，讓第二個數小的在前，這樣用LIS模闆就可以求出結果了。
代碼如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int,int> P;
P a[103];
int dp[103];
int cmp(P x,P y){
if(x.first!=y.first)return x.first<y.first;
else return x.second<y.second;
}
int judge(P x,P y){
if(x.first<=y.first&&x.second<y.second||x.first<y.first&&x.second<=y.second)return 1;
return 0;
}
int main(){
int t,n,x,y;
scanf("%d",&t);
while(t--){
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&x,&y);
if(x>y){a[i].first=y;a[i].second=x;}
else {a[i].first=x;a[i].second=y;}
dp[i]=1;
}
sort(a,a+n,cmp);
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(judge(a[j],a[i])){
dp[i]=max(dp[i],dp[j]+1);
}
}
res=max(res,dp[i]);
}
printf("%d\n",res);
}
}