http://acm.hdu.edu.cn/showproblem.php?pid=1160
DP,LIS
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 struct Point 5 { 6 int x, y, num; 7 }p[1234]; 8 9 int cmp(const void *a, const void *b) 10 { 11 return ((struct Point *)b)->x - ((struct Point *)a)->x; 12 } 13 14 int n, dp[1234], pre[1234], result; 15 16 int main() 17 { 18 int i, j, temp, flag; 19 for(i=1; ~scanf("%d%d", &p[i].x, &p[i].y); i++) 20 { 21 p[i].num = i; 22 } 23 n = i-1; 24 qsort(p+1, n, sizeof(p[0]), cmp); 25 result = pre[1] = dp[1] = 1; 26 for(i=2; i<=n; i++) 27 { 28 temp = 0; 29 flag = i; 30 for(j=1; j<i; j++) 31 { 32 if(p[j].y<p[i].y && p[j].x!=p[i].x && dp[j]>temp) 33 { 34 temp = dp[j]; 35 flag = j; 36 } 37 } 38 dp[i] = temp + 1; 39 pre[i] = flag; 40 if(dp[i] > dp[result]) 41 { 42 result = i; 43 } 44 } 45 printf("%d\n", dp[result]); 46 while(result != pre[result]) 47 { 48 printf("%d\n", p[result].num); 49 result = pre[result]; 50 } 51 printf("%d\n", p[result].num); 52 return 0; 53 }