P1233 木棍加工

本题链接：P1233 木棍加工

本博客给出本题截图：

AC代码

代码解释：按照长度从大到小排列，如果长度相同，则按照宽度从大到小进行排列，如此操作后，这个问题就变成了在n个数中，求不下降子序列最少个数，根据 dilworth定理：不下降子序列最小个数等于最大上升子序列的长度，故这个题就转换成了求n个数的最大上升子序列，f[i] 表示长度为 i 的(木棒宽度的)上升子序列结尾最小是多少，显然f是单调上升的，如果f数组的结尾元素小于a[i].w，那么就把a[i].w加入到f数组的结尾，反之利用二分法去找到当前比木棒宽度大的第一个位置并更新

代码*：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

struct dp
{
	int l, w;
}a[N];

int f[N];
int n, m;

bool cmp(dp b, dp c)
{
	if (b.l != c.l) return b.l > c.l;
	return b.w > c.w;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ )
		cin >> a[i].l >> a[i].w;
		
	sort(a + 1, a + n + 1, cmp);
	
	int cnt = 0;
	for (int i = 1; i <= n; i ++ )
	{
		if (a[i].w > f[cnt])
			f[++ cnt] = a[i].w;
		else
		{
			int t = lower_bound(f + 1, f + 1 + cnt, a[i].w) - f;
			f[t] = a[i].w;
		}
	}
	
	cout << cnt << endl;
	
	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

总结

dilworth定理：不下降子序列最小个数等于最大上升子序列的长度

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/119873656