题目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=1160
题目概述：
给出n对数据{w，s}，求一个严格上升的子序列，使长度最大并输出子序列中的元素的序号。
严格上升的定义：对于两对数据{w1，s1}和{w2，s2}，如果w1<w2&&s1>s2成立，则1<2.
大致思路：
就是求最长上升子序列，而且n也不是很大，O(n²)完全没问题。
需要注意的是应该先对数据的w按从小到大排序，问题就能转化成s的严格下降子序列了。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <vector> 6 #include <ctime> 7 #include <map> 8 #include <stack> 9 #include <queue> 10 #include <cstring> 11 #include <algorithm> 12 using namespace std; 13 14 #define sacnf scanf 15 #define scnaf scanf 16 #define scanfi(x) scanf("%d",&x) 17 #define scanfd(x) scanf("%lf",&x) 18 #define scanfl(x) scanf("%lld",&x) 19 #define scanfc(x) scanf("%c",&x) 20 #define scanfs(x) scanf("%s",x) 21 #define maxn 1010 22 #define maxm 10010 23 #define inf 1061109567 24 #define Eps 0.00001 25 const double PI=acos(-1.0); 26 #define mod 1000000007 27 #define MAXNUM 10000 28 void Swap(int &a,int &b) {int t=a;a=b;b=t;} 29 int Abs(int x) {return (x<0)?-x:x;} 30 typedef long long ll; 31 typedef unsigned int uint; 32 33 struct node 34 { 35 int w,s,pos; 36 bool operator < (const node &a) const 37 { 38 return (w<a.w)&&(s>a.s); 39 } 40 } a[maxn]; 41 42 bool cmp(node a,node b) {return a.w<b.w;} 43 44 int dp[maxn],pre[maxn]; 45 int step[maxn]; 46 47 int main() 48 { 49 //freopen("data.in","r",stdin); 50 //freopen("data.out","w",stdout); 51 //clock_t st=clock(); 52 int cnt=1; 53 while(~scanf("%d%d",&a[cnt].w,&a[cnt].s)) a[cnt].pos=cnt,cnt++; 54 int ans=-1,ansi=0;sort(a+1,a+cnt,cmp); 55 for(int i=1;i<cnt;i++) dp[i]=1,pre[i]=0; 56 for(int i=1;i<cnt;i++) 57 { 58 for(int j=1;j<i;j++) 59 if(a[j]<a[i]&&dp[i]<dp[j]+1) 60 { 61 dp[i]=dp[j]+1;pre[i]=j; 62 } 63 if(dp[i]>ans) 64 { 65 ans=dp[i];ansi=i; 66 } 67 } 68 printf("%d ",ans);cnt=0; 69 while(pre[ansi]!=0) 70 { 71 step[++cnt]=a[ansi].pos;ansi=pre[ansi]; 72 } 73 step[++cnt]=a[ansi].pos; 74 for(int i=cnt;i>=1;i--) printf("%d ",step[i]); 75 //clock_t ed=clock(); 76 //printf(" Time Used : %.5lf Ms. ",(double)(ed-st)/CLOCKS_PER_SEC); 77 return 0; 78 }