华师一附中OI组

标题: P1233 木棍加工 [打印本页]
作者: admin    时间: 2018-7-12 10:13
标题: P1233 木棍加工
https://www.luogu.org/problemnew/show/P1233
题目描述
一堆木头棍子共有n根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：

第一根棍子的准备时间为1分钟；

如果刚处理完长度为L，宽度为W的棍子，那么如果下一个棍子长度为Li，宽度为Wi，并且满足L>＝Li，W>＝Wi，这个棍子就不需要准备时间，否则需要1分钟的准备时间；

计算处理完n根棍子所需要的最短准备时间。比如，你有5根棍子，长度和宽度分别为(4, 9)，(5, 2)，(2, 1)，(3, 5)，(1, 4)，最短准备时间为2（按(4, 9)、(3, 5)、(1, 4)、(5, 2)、(2, 1)的次序进行加工）。

输入输出格式
输入格式：
第一行是一个整数n(n<＝5000)，第2行是2n个整数，分别是L1，W1，L2，w2，…，Ln，Wn。L和W的值均不超过10000，相邻两数之间用空格分开。

输出格式：
仅一行，一个整数，所需要的最短准备时间。

输入输出样例
输入样例#1：
5
4 9 5 2 2 1 3 5 1 4
输出样例#1：
2

作者: Scorpio    时间: 2018-7-13 18:40
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int f[5250];
  5. int i,j,n,s;
  6. struct stick
  7. {
  8.     int l,w;
  9. }a[5250];
  10. bool compare(stick aa,stick bb)
  11. {
  12.     if(aa.l==bb.l)
  13.         return aa.w<bb.w;
  14.     return aa.l<bb.l;
  15. }
  16. int main()
  17. {
  18.     cin>>n;
  19.     for(i=1;i<=n;i++)
  20.         cin>>a[i].l>>a[i].w;
  21.     sort(a+1,a+n+1,compare);
  22.     for(i=1;i<=n;i++)
  23.     {
  24.         f[i]=1;
  25.         for(j=1;j<=i;j++)
  26.             if(a[i].w<a[j].w)
  27.                 f[i]=max(f[j]+1,f[i]);
  28.     }
  29.     for(i=1;i<=n;i++)
  30.         s=max(s,f[i]);
  31.     cout<<s;
  32.     return 0;
  33. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-7-15 08:59
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. int i,n,j,ans,f[5050];
  6. struct mg
  7. {
  8.     int l,w;
  9. }a[5050];
  10. bool cmp(mg x,mg y)
  11. {
  12.     return x.l>y.l;
  13. }
  14. int main()
  15. {
  16.     cin>>n;
  17.     for(i=1;i<=n;i++)
  18.     cin>>a[i].l>>a[i].w;
  19.     sort(a+1,a+n+1,cmp);
  20.     for(i=1;i<=n;i++)
  21.         f[i]=1;
  22.     for(i=2;i<=n;i++)
  23.     {
  24.         for(j=1;j<=i-1;j++)
  25.         {
  26.             if(a[j].w<a[i].w)
  27.                 f[i]=max(f[i],f[j]+1);
  28.         }
  29.     }
  30.     for(i=1;i<=n;i++)
  31.         ans=max(ans,f[i]);
  32.     cout<<ans;
  33.     return 0;
  34. }

复制代码
作者: 黄煦喆    时间: 2018-7-29 11:46
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int n;
  5. bool b[5001];
  6. struct stick
  7. {
  8.     int l,w;
  9. } a[5001];
  10. bool cmp(stick const &x,stick const &y)
  11. {
  12.     if(x.l==y.l)return x.w>y.w;
  13.     return x.l>y.l;
  14. }
  15. int main()
  16. {
  17.     cin>>n;
  18.     for(int i=1; i<=n; i++)cin>>a[i].l>>a[i].w;
  19.     sort(a+1,a+n+1,cmp);
  20.     for(int i=1; i<n; i++)
  21.         if(!b[i])
  22.         {
  23.             int k=a[i].w;
  24.             for(int j=i+1; j<=n; j++)
  25.                 if(b[j])continue;
  26.                 else if(a[j].w<=k)
  27.                 {
  28.                     b[j]=1;
  29.                     k=a[j].w;
  30.                 }
  31.         }
  32.     int ans=0;
  33.     for(int i=1; i<=n; i++)if(!b[i])ans++;
  34.     cout<<ans;
  35.     return 0;
  36. }
复制代码
作者: 吴语林    时间: 2018-7-29 19:36
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. struct node
  14. {
  15.         int l,w;
  16. }a[6000];
  17. int n,f[6000],ans=-1;
  18. bool cmp(node x,node y)
  19. {
  20.         if(x.l!=y.l)
  21.                 return x.l<y.l;
  22.         return x.w<y.w;
  23. }
  24. int main()
  25. {
  26.         scanf("%d",&n);
  27.         for(int i=1;i<=n;i++)
  28.                 scanf("%d%d",&a[i].l,&a[i].w);
  29.         sort(a+1,a+1+n,cmp);
  30.         for(int i=1;i<=n;i++)
  31.     {
  32.         f[i]=1;
  33.             for(int j=1;j<i;j++)
  34.             {
  35.                 if(a[j].w>a[i].w)
  36.                                 f[i]=max(f[j]+1,f[i]);
  37.             }
  38.     }
  39.     for(int i=1;i<=n;i++)
  40.                 ans=max(ans,f[i]);
  41.         printf("%d",ans);
  42.     return 0;
  43. }
复制代码
作者: ZMQ    时间: 2018-8-3 22:51
提示: 作者被禁止或删除 内容自动屏蔽



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2