P1233 木棍加工题解

题目传送门。

1.题外话

dp掌握不够好，最近在题单里从dp入门开始刷~

2.解题意

木棍套娃，如果不能套了就要进行1分钟准备。所以说是每一段最长不上升子序列对应一分钟，求的总准备时间就是最长不上升子序列的个数。

3.找思路

首先看到这种题面，我们不难根据以往经验想到排序。要满足木棍的长度一个比一个小，我们可以先拿长度l由大到小排序，这样所有的l都满足了形成套娃的条件。于是我们只用对宽度w讨论即可，l就可以不用管了。

对于宽度w，考虑套娃的条件，不难得知只有当w[i-1]>w[i]时才能套娃，也就是让我们求最长不上升子序列。答案是准备时间，前面我们已经讲了准备时间就是最长不上升子序列个数。于是答案让我们求的就是关于w的最长不上升子序列个数。

根据dilworth定理可知，最长不上升子序列个数=最长上升子序列长度。

dilworth下方有我推荐的讲解链接，如果不会dilworth，也可以这样简单理解：从每一个最长不上升子序列中抽一个元素，就组成最长上升子序列了。那么最长上升子序列长度就是最长不上升子序列的个数。当然这是一种想当然的理解。要找的话肯定还需要更细的方案才行。

于是我们用nlogn算法求出w的最长上升子序列长度并输出即可。

总体步骤：

1.建立结构体，cmp比较函数，读入数据

2.sort按照cmp排序

3.nlogn求最长上升子序列长度

就是这么简单。

关于dilworth定理，我从网上随机找了一名dalao的博客，读了读，比较简单易懂。

4.Code

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define ll long long
 6 #define re register
 7 #define N 5010
 8 using namespace std;
 9 inline int read()
10 {
11     int x=0,f=1; char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 int n,f[N],ans;
17 struct stick{
18     int l,w;
19 }s[N];
20 bool cmp(stick a,stick b)
21 {
22     return a.l>b.l;
23 }
24 int main()
25 {
26     n=read();
27     for(int i=1;i<=n;i++)
28         s[i].l=read(),s[i].w=read();
29     sort(s+1,s+1+n,cmp);
30     for(int i=1;i<=n;i++)
31     {
32         if(s[i].w>f[ans])
33             f[++ans]=s[i].w;
34         else
35         {
36             int l=1,r=ans;
37             while(l<r)
38             {
39                 int mid=(l+r)>>1;
40                 if(f[mid]>=s[i].w)r=mid;
41                 else l=mid+1;
42             }
43             f[l]=s[i].w;
44         }
45     }
46     printf("%d",ans);
47     return 0;
48 }

View Code

完结撒花。

P1233 木棍加工 题解

P1233 木棍加工题解