题意：求限定起始位置的二维最长递增子序列.
解题思路：直接DP
解题代码：
1 // File Name: 4d.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月04日 星期一 19时24分49秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 28 struct node{ 29 int from; 30 int len; 31 }dp[5000]; 32 struct node1{ 33 int w, h,s; 34 }a[5005]; 35 int ok[10000]; 36 int cmp(node1 a,node1 b) 37 { 38 if(a.w == b.w) 39 return a.h < b.h; 40 return a.w < b.w; 41 } 42 void dfs(int k) 43 { 44 if(k == -1) 45 return; 46 dfs(dp[k].from); 47 if(a[k].s) 48 printf("%d ",a[k].s); 49 50 } 51 int main(){ 52 int n ; 53 scanf("%d %d %d",&n,&a[0].w,&a[0].h); 54 memset(ok,0,sizeof(ok)); 55 for(int i =1 ;i <= n;i ++) 56 { 57 scanf("%d %d",&a[i].w,&a[i].h); 58 a[i].s = i; 59 } 60 sort(a+1,a+1+n,cmp); 61 /* for(int i = 1;i <= n;i ++) 62 { 63 printf("%d %d ",a[i].w,a[i].h); 64 }*/ 65 for(int i = 0 ;i <= n;i ++) 66 { 67 dp[i].from = i ; 68 dp[i].len = 1; 69 } 70 dp[0].from = -1; 71 ok[0] = 1; 72 int asite = 0; 73 int amx = 1; 74 for(int i = 1;i <= n;i ++) 75 { 76 int mx = 0; 77 int site = -1 ; 78 for(int j = 0;j < i;j ++) 79 { 80 if(a[i].w > a[j].w && a[i].h > a[j].h && ok[j]) 81 { 82 ok[i] = 1; 83 if(dp[j].len > mx) 84 { 85 mx = dp[j].len; 86 site = j; 87 } 88 } 89 } 90 dp[i].len = mx +1; 91 dp[i].from = site; 92 if(dp[i].len > amx) 93 { 94 amx = dp[i].len ; 95 asite = i; 96 } 97 //printf("%d ",dp[i].len); 98 } 99 printf("%d ",amx-1); 100 dfs(asite); 101 return 0; 102 }