ZOJ Problem Set - 1025

时间：2011-01-18 来源：长江西岸

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, ..., ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

Output

The output should contain the minimum setup time in minutes, one per line.

Sample Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

Output for the Sample Input

2
1
3

#include <stdio.h>
#include <iostream>
using namespace std;

int s[5000][2];

void sort(int N)
{
        int i, j, t[2];
        for(i=1; i<N; i++)
        {
                t[0] = s[i][0];
                t[1] = s[i][1];
                for(j=i-1; j>=0; j--)
                {
                        if(t[0] < s[j][0] || t[0] == s[j][0] && t[1] < s[j][1])
                        {
                                s[j+1][0] = s[j][0];
                                s[j+1][1] = s[j][1];
                        }
                        else break;
                }
                s[j+1][0] = t[0];
                s[j+1][1] = t[1];               
        }
}


int main()
{
        int T;
        cin >> T;
        for(int t=0; t<T; t++)
        {
                int N;
                cin >> N;
                for(int n=0; n<N; n++)
                        cin >> s[n][0] >> s[n][1];
                sort(N);
                int count = 0;
                while(1)
                {
                        int i = 0;
                        while(i<N && s[i][0] == -1) i++;
                        if(i==N) break;
                        int cur[2];
                        cur[0] = s[i][0];
                        cur[1] = s[i][1];
                        s[i][0] = -1;
                        for(; i<N; i++)
                        {
                                if(s[i][0] != -1 && s[i][0] >= cur[0] && s[i][1] >= cur[1])
                                {
                                        cur[0] = s[i][0];
                                        cur[1] = s[i][1];
                                        s[i][0] = -1;
                                }
                        }
                        count ++;
                }
                cout << count << endl;
        }
        return 0;
}

这题用贪心算法可以实现全局最优。排个序，然后就能看出，每次找出的子序列都是无争议的最终情况。

搞个循环，把所有子序列都找出即可。