poj 1065 贪心或者动态规划

偏执的太偏执、 2022-08-03 11:55 200阅读 0赞

Wooden Sticks

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 19566</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 8255</td> 
  </tr> 
 </tbody> 
</table>

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][]

这题很像杭电上的最小拦截系统，可以使用贪心或者动态规划来求解。

动态规划来求解原理可以查看[这里][Link 1]  ，把问题转化为求按照长度排序之后求w的最长递减子序列。

有两种做法。一种是O（n^2）的，另一种是O（nlogn）的。

贪心算法求解：

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    struct st
    {
        int l,w;
    }a[5055];
    bool vis[5005];
    bool cmp(const st &a,const st &b)
    {
        if(a.l!=b.l)return a.l<b.l;return a.w<b.w;
    }
    int main()
    {
    
    
        int T=in();
        while(T--)
        {
            int n=in();
            for(int i=0;i<n;i++)
            {
                a[i].l=in(),a[i].w=in();
            }
            sort(a,a+n,cmp);
            mem(vis,0);
            int ans=0;
            for(int i=0;i<n;i++)
            {
                if(!vis[i])
                {
                    ans++;
                    int t=a[i].w;
                    for(int j=i;j<n;j++)
                    {
                        if(!vis[j] && a[j].w>=t)
                        {
                            vis[j]=1;
                            t=a[j].w;//别漏了！
                        }
                    }
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    
    }

最长递减子序列n^2的版本：

//poj1065
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    struct st
    {
        int l,w;
    }a[5055];
    
    bool cmp(const st &a,const st &b)
    {
        if(a.l!=b.l)return a.l<b.l;return a.w<b.w;
    }
    
    int dp[5055]; //dp【i】表示前i个元素中最长递减子序列
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in();
            for(int i=0;i<n;i++)
               a[i].l=in(),a[i].w=in();
            sort(a,a+n,cmp);
            mem(dp,0); 
            for(int i=0;i<n;i++)
            {
                dp[i]=1;
                for(int j=0;j<i;j++)
                    if(a[i].w<a[j].w)
                        dp[i]=max(dp[i],dp[j]+1);
            }
            int ans=0;
            for(int i=0;i<n;i++)ans=max(ans,dp[i]);
            cout<<ans<<endl;
        }
        return 0;
    }

最长递减子序列O(Nlongn)版本：

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    struct st
    {
        int l,w;
    }a[5055];
    
    bool cmp(const st &a,const st &b)
    {
        if(a.l!=b.l)return a.l<b.l;return a.w<b.w;
    }
    
    int dp[5055];
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in();
            for(int i=0;i<n;i++)
               a[i].l=in(),a[i].w=in();
            sort(a,a+n,cmp);
            mem(dp,-1);
            for(int i=0;i<n;i++)
            {
                *lower_bound(dp,dp+n,a[i].w,greater<int>())=a[i].w;
            }
            printf("%d\n",lower_bound(dp,dp+n,-1,greater<int>())-dp);
    
        }
        return 0;
    }

[Taejon 2001]: http://poj.org/searchproblem?field=source&key=Taejon+2001
[Link 1]: http://www.hankcs.com/program/cpp/poj-1065-wooden-sticks.html