最长递增子序列
这到题给我的启发是：
1，最长递增子序列实际上就是不知道起点的动规模型。
2，动规运用在有序的数据上（如果不对矩形进行排序处理，就没有“前面的矩形不可能包含后面矩形的断言”==“前面的数小于后面的数”）
做法：排序+最长递增子序列
动规方程： f[i]=max(f[j]+1)(1<=j<i, a[j]<a[i]&&b[j]<b[i]) ==最长递增子序列的动规方程
1 #include <stdio.h> 2 int a[1001], b[1001], f[1001]; 3 void qsort(int l, int r) 4 { 5 int x, y, mid1, mid2, temp; 6 mid1=a[(l+r)/2]; 7 mid2=b[(l+r)/2]; 8 x=l; 9 y=r; 10 while(x<=y) 11 { 12 while(a[x]<mid1||(a[x]==mid1&&b[x]<mid2)) x++; 13 while(a[y]>mid1||(a[y]==mid1&&b[y]>mid2)) y--; 14 if(x<=y) 15 { 16 temp=a[x]; 17 a[x]=a[y]; 18 a[y]=temp; 19 temp=b[x]; 20 b[x]=b[y]; 21 b[y]=temp; 22 x++; 23 y--; 24 } 25 } 26 if(l<y) qsort(l, y); 27 if(x<r) qsort(x, r); 28 } 29 int main() 30 { 31 int n, i, k, temp, ans=1; 32 scanf("%d", &n); 33 for(i=1; i<=n; i++) 34 { 35 scanf("%d%d", &a[i], &b[i]); 36 if(a[i]<b[i]) 37 { 38 temp=a[i]; 39 a[i]=b[i]; 40 b[i]=temp; 41 } 42 } 43 qsort(1, n); 44 for(i=1; i<=n; i++) 45 { 46 for(k=1; k<i; k++) 47 { 48 if(a[i]>a[k]&&b[i]>b[k]&&f[k]+1>f[i]) 49 { 50 f[i]=f[k]+1; 51 } 52 } 53 if(f[i]>ans) ans=f[i]; 54 } 55 printf("%d", ans+1); 56 return 0; 57 }