poj -1065 Wooden Sticks （贪心or dp）

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

题意比较简单，有n跟木棍，事先知道每根木棍的长度和宽度，这些木棍需要送去加工，第一根木棍需要一分钟的生产时间，如果当前木棍的长度跟宽度

都大于前一根木棍，那么这根木棍不需要生产时间，问你最少的生产时间是多少？

首先可以贪心，先按长度 l排序，如果l相同，按宽度w排序。

从i=0开始，每次把接下来的i+1 - n-1 的没有标记并且长度和宽度大于等于i这根木棍的长度和宽度标记起来。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 struct point

 {

     int l,w;

     bool operator < (const point &a) const

     {

         return l==a.l ? w<a.w : l<a.l;

     }

 }p[maxn];

 int mark[maxn];

 int main()

 {

     int t,n;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         for(int i=;i<n;i++)

         {

             scanf("%d%d",&p[i].l,&p[i].w);

         }

         sort(p,p+n);

         //for(int i=0;i<n;i++) printf("%d %d\n",p[i].l,p[i].w);

         int s=;

         memset(mark,,sizeof(mark));

         for(int i=;i<n;i++)

         {

             int temp=p[i].w;

             if(!mark[i])

             {

                 for(int j=i+;j<n;j++)

                 {

                     if(p[j].w>=temp&&!mark[j])

                     {

                         temp=p[j].w;

                         mark[j]=;

                     }

                 }

                 s++;

             }

         }

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

     }

     return ;

 }

dp：排序跟上面一样，然后就是找 w 的最长下降子序列。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 struct point

 {

     int l,w;

     bool operator < (const point &a) const

     {

         return l==a.l ? w<a.w : l<a.l;

     }

 }p[maxn];

 int dp[maxn];

 int main()

 {

     int t,n;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         for(int i=;i<n;i++)

         {

             scanf("%d%d",&p[i].l,&p[i].w);

         }

         sort(p,p+n);

         //for(int i=0;i<n;i++) printf("%d %d\n",p[i].l,p[i].w);

         int ans=;

         for(int i=;i<n;i++) dp[i]=;

         for(int i=;i<n;i++)

         {

             for(int j=;j<i;j++)

                 if(p[j].w>p[i].w) dp[i]=max(dp[i],dp[j]+);

             ans=max(ans,dp[i]);

         }

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

     }

     return ;

 }

巴特西

poj -1065 Wooden Sticks （贪心or dp）

最新文章

热门文章