POJ_1065_Wooden_Sticks_(动态规划,LIS+鸽笼原理)

描述

木棍有重量 w 和长度 l 两种属性,要使 l 和 w 同时单调不降,否则切割机器就要停一次,问最少停多少次(开始时停一次).

Wooden Sticks

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 21277		Accepted: 9030

Description

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l <= l' and w <= w'. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .

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 2n 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

Sample Output

2
1
3

Source

Taejon 2001

分析

神原理...

要求最少停多少次,就是要求单调不降的子序列的个数 x 最多为多少(每次停完都是一个单调不降的子序列),问题转化为求 x 的最小值.

我们现将木棍按照其中一种属性升序(不降)排序,这时另一种属性的最长下降子序列的长度记为 L .可以证明 x >=L.(鸽笼原理).

详细题解:

http://www.hankcs.com/program/cpp/poj-1065-wooden-sticks.html

注意:

1.二分的边界.在找满足 a [ k ] <= -1 的 k 的最小值时,可能 dp 数组中已经没有 -1 了,也就是 n 个位置全部被占满了,也就是整个序列就是一个下降序列,此时会找到 n 的位置,再 -1 答案就错误了,所以开始的时候将 1 ~ n + 1 都赋为 -1 ,之后 dp 时查找在 1 ~ n 查找,因为 dp 结束之前最多是 n - 1 个,不会把 dp 数组填满,数组中一定还有 -1 ,就一定存在满足 a [ k ] <= v (v>0) 的 k ,计算总长度时在 1~n+1 查找,确保有满足 a [ k ] <= -1 的 k .

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define read(a) a=getnum()
 4 #define for1(i,a,n) for(int i=(a);i<=(n);i++)
 5 using namespace std;
 6 
 7 const int maxn=5005;
 8 struct node {int l,w;}wood[maxn];
 9 int q,n;
10 int dp[maxn];
11 
12 inline int getnum(){ int r=0,k=1;char c;for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') k=-1;for(;c>='0'&&c<='9';c=getchar()) r=r*10+c-'0'; return r*k; }
13 
14 bool comp(node x,node y) { return x.l<y.l; }
15 
16 int bsearch(int l,int r,int v)
17 {
18     while(l<r)
19     {
20         int m=l+(r-l)/2;
21         if(dp[m]<=v) r=m;
22         else l=m+1;
23     }
24     return l;
25 }
26 
27 void solve()
28 {
29     sort(wood+1,wood+n+1,comp);
30     for1(i,1,n+1) dp[i]=-1;
31     for1(i,1,n)
32     {
33         int idx=bsearch(1,n,wood[i].w);
34         dp[idx]=wood[i].w;
35     }
36     int ans=bsearch(1,n+1,-1)-1;
37     printf("%d
",ans);
38 }    
39 
40 void init()
41 {
42     read(q);
43     while(q--)
44     {
45         read(n);
46         for1(i,1,n) { read(wood[i].l); read(wood[i].w); }
47         solve();
48         
49     }
50 }
51 
52 int main()
53 {
54 #ifndef ONLINE_JUDGE
55     freopen("wood.in","r",stdin);
56     freopen("wood.out","w",stdout);
57 #endif
58     init();
59 #ifndef ONLINE_JUDGE
60     fclose(stdin);
61     fclose(stdout);
62     system("wood.out");
63 #endif
64     return 0;
65 }

View Code