这次的题目 , 我最初是想用 NlogN 的那个算法去做 结果数值覆盖那里出了问题 , 由于 : 1 ,我自己的理解不够 . 2 :算法自身的局限 , 导致是在想不出来 解决的办法 , 先把代码附上 , 这次还是用的 lower_bound 代码长度还行 ,
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack> 10 #include<string> 11 #include<sstream> 12 #include<map> 13 #include<cctype> 14 #include<limits.h> 15 using namespace std; 16 struct node 17 { 18 int x,y; 19 }a[15]; 20 bool cmp(node a,node b) 21 { 22 if(a.x<b.x) 23 return true; 24 else 25 if(a.x==b.x&&a.y<b.y) 26 return true; 27 return false; 28 } 29 int x[15],y[15],dpx[15],dpy[15]; 30 int main() 31 { 32 int t,n; 33 scanf("%d",&t); 34 while(t--) 35 { 36 scanf("%d",&n); 37 for(int i=0;i<n;i++) 38 { 39 int x1,y1; 40 scanf("%d%d",&x1,&y1); // 让 x 尽量的大 . 41 if(x1>y1) 42 swap(x1,y1); 43 a[i].x=x1,a[i].y=y1; // 尽量的 让 x 大 44 } // 然后开始 排序 45 sort(a,a+n,cmp); // 排序之后 就 从大到小找 递减子序列 46 for(i=0;i<n;i++) 47 { 48 x[i]=a[i].x,y[i]=a[i].y; // 将他 输入到 两个数组当中 开始 用 lower_bound 49 } 50 int num=0,locationx,locationy; 51 for(i=0;i<n;i++) 52 { 53 locationx=lower_bound(dpx,dpx+num,x[i])-dpx; 54 locationy=lower_bound(dpy,dpy+num,y[i])-dpy; 55 if(locationx==locationy) 56 { 57 dpx[locationx]=x[i]; 58 dpy[locationy]=y[i]; 59 num=locationx+1>num?locationx+1:num; 60 } 61 } 62 printf("%d ",num); 63 } 64 return 0; 65 }
这一组测试数据出了问题. 5 15 94 13 11 33 12 9 49 62 14
可以发现 按照 x 或 y 中的一个数字排序的时候 另一个数字的大小 会特别的大 , ,然后 这样的顺序就不是 , 能嵌套最多的 顺序了 , 可以发现这一道题 , 如果做的时候 所依据的算法 要依赖顺序的话 是 十分 让人难受的 , 看了看 别人做的 , 大部分都是N^2 的时间复杂度 . 想起来自己以前做的 最少导弹拦截系统 , 也是不用考虑
最早的时候我想的是 将他们排序 , 排序的函数是
bool cmp(node a,node b) { if(a.x<b.x) return true; else if(a.x==b.x&&a.y<b.y) return true; return false; }
然后用用二分法 , 按照最长递增子序列的方法 , 找出来最长递增 嵌套 矩形 . 但是在实现的时候 和 一维的 最长递增子序列 有很大的区别 下面附上 一维最长递增子序列的 核心代码 .
for(int i=0;i<n;i++) { scanf("%d",&b); location=lower_bound(dp,dp+num,b)-dp; //在 已经有序的数组中二分查找 dp[location]=b; num=location+1>num?location+1:num; }
二维的话 , 代码如下
1 for(i=0;i<n;i++) 2 { 3 locationx=lower_bound(dpx,dpx+num,x[i])-dpx; 4 locationy=lower_bound(dpy,dpy+num,y[i])-dpy; 5 if(locationx==locationy) 6 { 7 dpx[locationx]=x[i]; 8 dpy[locationy]=y[i]; 9 num=locationx+1>num?locationx+1:num; 10 } 1
将这两个 代码进行对比可以发现 ，第一个 代码之中的 数据元素都能进入 dp 数组 然而第二个 代码可以看出 ， 有些数据元素 不能进入 dp数组 ， 就这样导致了错误。 ， 具体错误 可以 用我上面 给出的 完整代码和 数据 进行 调试 看出来 。 然后我就又想了想 ， 发现这个代码不正确的原因就是 排序的错误 ， 如果排序正确的话 ， 是不会 出现这样的情况的 。
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<set> #include<stack> #include<string> #include<sstream> #include<map> #include<cctype> #include<limits.h> using namespace std; // 奇妙奇妙真奇妙 struct node { int x,y; // 按照 最少拦截系统的思路来说 , }; bool cmp(node a,node b) { if(a.x<b.x) return true; else if(a.x==b.x&&a.y<b.y) return true; return false; } int main() { int t,n,dp[1005]; node a[1005]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) { int x1,y1; scanf("%d%d",&x1,&y1); // 让 x 尽量的大 . if(x1>y1) swap(x1,y1); a[i].x=x1,a[i].y=y1; // 尽量的 让 x 大 } // 然后开始 排序 sort(a,a+n,cmp); // 排序之后 就 从大到小找 递减子序列 for(int i=0;i<=n;i++) dp[i]=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(a[i].x>a[j].x&&a[i].y>a[j].y&&dp[i]<dp[j]+1) dp[i]=dp[j]+1; } } int maxn=INT_MIN; for(int i=0;i<n;i++) maxn=max(maxn,dp[i]); printf("%d ",maxn); } return 0; }
下面是玉民大大写的 , 一道题的解法还是很多的 , 有时候不能想的 太复杂了 , 这就是一个 很简单的想法
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<set> #include<stack> #include<string> #include<sstream> #include<map> #include<cctype> #include<limits.h> using namespace std; struct node { int x,y; }a[1005]; bool cmp(node a,node b) { if(a.x<b.x) return true; return false; } int main() { int t,n,dp[1005]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) { int x1,y1; scanf("%d%d",&x1,&y1); // 让 x 尽量的大 . if(x1>y1) swap(x1,y1); dp[i]=1; a[i].x=x1,a[i].y=y1; // 尽量的 让 x 大 } // 然后开始 排序 sort(a,a+n,cmp); // 排序之后 就 从大到小找 递减子序列 for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(a[i].x>a[j].x&&a[i].y>a[j].y) dp[i]=dp[i]>dp[j]+1?dp[i]:dp[j]+1; } } int maxn=INT_MIN; for(int i=0;i<n;i++) maxn=maxn>dp[i]?maxn:dp[i]; printf("%d ",maxn); } return 0; }