- 输入
- 第一行是一个正正数N(0<N<10),表示测试数据组数,
每组测试数据的第一行是一个正正数n,表示该组测试数据中含有矩形的个数(n<=1000)
随后的n行,每行有两个数a,b(0<a,b<100),表示矩形的长和宽 - 输出
- 每组测试数据都输出一个数,表示最多符合条件的矩形数目,每组输出占一行
样例输入
1 10 1 2 2 4 5 8 6 10 7 9 3 1 5 8 12 10 9 7 2 2
- 样例输出
-
5
求最长上升子序列,只不过是处理二维的,和一维并无太大区别,属于简单动态规划中的一种。
#include <iostream> #include <algorithm> using namespace std; #define MAX 1005 typedef struct Point{ int x; int y; }Point; bool cmp(Point a, Point b) { if(a.x == b.x) { return a.y < b.y; } else { return a.x < b.x; } } int LIS(Point arr[], int n) { int dp[MAX]; for(int i=1; i<=n; ++i) dp[i] = 0; dp[1] = 1; for(int i=2; i<=n; ++i) { for(int j=1; j<i; ++j) { if(arr[i].x>arr[j].x && arr[i].y > arr[j].y && dp[j]>dp[i]) dp[i] = dp[j]; } dp[i] = dp[i]+1; } int ans = 0; for(int i=1; i<=n; ++i) { if(dp[i] > ans) ans = dp[i]; } return ans; } int main() { freopen("in.txt", "r", stdin); int t, n, i, x, y; Point array[MAX]; cin >> t; while(t--) { cin >> n; for(i = 1; i <= n; i++) { cin >> x >> y; if(x > y) { array[i].x = y; array[i].y = x; } else { array[i].x = x; array[i].y = y; } } sort(array + 1, array + n + 1, cmp); cout << LIS(array, n) << endl; } }
算法竞赛入门经典中提到记忆化搜索的方法:
#include <iostream> #include <string.h> using namespace std; int G[1010][1010]; int d[1010]; int dp(int i,int n){ int &ans=d[i]; if(ans>0) return ans; ans=1; for(int j=1;j<=n;j++) if(G[i][j]) if(ans<dp(j,n)+1) ans=dp(j,n)+1; return ans; } int main() { int N; cin>>N; while(N--){ int n,a[1010],b[1010]; memset(G,0,sizeof(G)); memset(d,0,sizeof(d)); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((a[i]>a[j]&&b[i]>b[j])||(a[i]>b[j]&&b[i]>a[j])) G[i][j]=1; int max=0; for(int i=1;i<=n;i++) if(dp(i,n)>max) max=dp(i,n); cout<<max<<endl; } return 0; }
打印结果:#include <iostream> #include <string.h> using namespace std; int G[1010][1010]; int d[1010]; int n; int dp(int i){ int &ans=d[i]; if(ans>0) return ans; ans=1; for(int j=1;j<=n;j++) if(G[i][j]) if(ans<dp(j)+1) ans=dp(j)+1; return ans; } void print_ans(int i){ printf("%d ",i); for(int j=1;j<=n;j++) if(G[i][j]&&d[i]==d[j]+1){ print_ans(j); break; } } int main() { int N; cin>>N; while(N--){ int a[1010],b[1010]; memset(G,0,sizeof(G)); memset(d,0,sizeof(d)); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((a[i]>a[j]&&b[i]>b[j])||(a[i]>b[j]&&b[i]>a[j])) G[i][j]=1; int max=0,max_i=0; for(int i=1;i<=n;i++) if(dp(i)>max) { max=dp(i); max_i=i; } print_ans(max_i); cout<<endl; } return 0; }
矩形嵌套
Keep it simple!