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

时间：2022-07-03 08:35:28

描述

http://poj.org/problem?id=1065

木棍有重量 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

分析

神原理...

要求最少停多少次,就是要求单调不降的子序列的个数 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 .

 #include<cstdio>

 #include<algorithm>

 #define read(a) a=getnum()

 #define for1(i,a,n) for(int i=(a);i<=(n);i++)

 using namespace std;

 const int maxn=;

 struct node {int l,w;}wood[maxn];

 int q,n;

 int dp[maxn];

 inline int getnum(){ int r=,k=;char c;for(c=getchar();c<''||c>'';c=getchar()) if(c=='-') k=-;for(;c>=''&&c<='';c=getchar()) r=r*+c-''; return r*k; }

 bool comp(node x,node y) { return x.l<y.l; }

 int bsearch(int l,int r,int v)

 {

     while(l<r)

     {

         int m=l+(r-l)/;

         if(dp[m]<=v) r=m;

         else l=m+;

     }

     return l;

 }

 void solve()

 {

     sort(wood+,wood+n+,comp);

     for1(i,,n+) dp[i]=-;

     for1(i,,n)

     {

         int idx=bsearch(,n,wood[i].w);

         dp[idx]=wood[i].w;

     }

     int ans=bsearch(,n+,-)-;

     printf("%d\n",ans);

 }    

 void init()

 {

     read(q);

     while(q--)

     {

         read(n);

         for1(i,,n) { read(wood[i].l); read(wood[i].w); }

         solve();

     }

 }

 int main()

 {

 #ifndef ONLINE_JUDGE

     freopen("wood.in","r",stdin);

     freopen("wood.out","w",stdout);

 #endif

     init();

 #ifndef ONLINE_JUDGE

     fclose(stdin);

     fclose(stdout);

     system("wood.out");

 #endif

     return ;

 }

相关文章