FatMouse's Speed

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7816 Accepted Submission(s): 3470
Special Judge

Problem Description FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.

Input Input contains data for a bunch of mice, one mouse per line, terminated by end of file.

The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.

Two mice may have the same weight, the same speed, or even the same weight and speed.

Output Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],..., m[n] then it must be the case that

W[m[1]] < W[m[2]] < ... < W[m[n]]

and

S[m[1]] > S[m[2]] > ... > S[m[n]]

In order for the answer to be correct, n should be as large as possible.

All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.

Sample Input

Sample Output

hdu 1160 题目大意：求出最长的串使得，串里面任意的i s[j]。
解题思路：我们根据w先排个序然后对s求一个严格递减就可以了，由于n最大为1000，可以采取O（n*n）的算法。然后输出序列记住路径就可以了。详见代码。
题目地址：FatMouse's Speed
AC代码：

#include
   
    
#include
    
      #include
     
       #include
      
        using namespace std; int index[1005]; int dp[1005]; int ans[1005]; struct node { int a; int b; int pos; }nod[1005]; int cmp(node p1,node p2) { if(p1.a
       
        p2.b) return 1; return 0; } void debug() { int i; cout<<"******"<
        
         >p1>>p2) { nod[n].a=p1; nod[n].b=p2; nod[n].pos=n+1; n++; } sort(nod,nod+n,cmp); //memset(dp,1,sizeof(dp)); //debug(); for(i=0;i<=1000;i++) { dp[i]=1; index[i]=0; } int tmp,ma=1; for(i=0;i
         
          nod[j].b) { if(dp[i]+1>dp[j]) { dp[j]=dp[i]+1; if(dp[j]>ma) { ma=dp[j]; tmp=j; } index[j]=i; } } } //cout<
          
           =0;i--) cout<
           
            
 
            
 
             Constructing Roads In JGShining's Kingdom 
            Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
 Total Submission(s): 13635 Accepted Submission(s): 3877
 
            
 
            
 Problem Description JGShining's kingdom consists of 2n(n is no more than 500,000) small cities which are located in two parallel lines.
            
 
            
 Half of these cities are rich in resource (we call them rich cities) while the others are short of resource (we call them poor cities). Each poor city is short of exactly one kind of resource and also each rich city is rich in exactly one kind of resource. You may assume no two poor cities are short of one same kind of resource and no two rich cities are rich in one same kind of resource. 
            
 
            
 With the development of industry, poor cities wanna import resource from rich ones. The roads existed are so small that they're unable to ensure the heavy trucks, so new roads should be built. The poor cities strongly BS each other, so are the rich ones. Poor cities don't wanna build a road with other poor ones, and rich ones also can't abide sharing an end of road with other rich ones. Because of economic benefit, any rich city will be willing to export resource to any poor one.
            
 
            
 Rich citis marked from 1 to n are located in Lin

hdu 1025&hdu 1025 LIS(O(n*n)和O(n*log(n)))两种解法(一)

FatMouse's Speed

Constructing Roads In JGShining's Kingdom

hdu 1025&hdu 1025 LIS(O(nn)和O(nlog(n)))两种解法(一)