输出 #1 复制 2
这个题有很多种方法, 在洛谷的题解里有贪心, 动归. 这个题还涉及到了一个知识最长上升子序列和最长不下降子序列.
有一个规律: 同一个序列的最长升序子序列的最小划分 == 这个序列的最长降序子序列的包含元素的个数.
法一: 贪心
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #pragma warning(disable:4996)
- using namespace std;
- struct stick {
- int L;
- int W;
- };
- stick a[5005];
- int book[5005];
- bool cmp(stick a, stick b)
- {
- if (a.L == b.L)return a.W> b.W;
- return a.L> b.L;
- }
- int main(){
- int n;
- scanf("%d", &n);
- for (int i = 1; i <= n; ++i)
- scanf("%d %d", &a[i].L, &a[i].W);
- sort(a + 1, a + n + 1, cmp);
- for (int i = 1; i <= n; ++i)
- book[i] = 0;
- int cut;
- for (int i = 1; i <= n; i++) {
- if (book[i] == 0) {
- cut = a[i].W;
- for (int j = i+1; j <= n; j++) {
- if (a[j].W <= cut&&book[j] == 0) {
- book[j] = 1;
- cut = a[j].W;
- }
- }
- }
- }
- int time = 0;
- for (int i = 1; i <= n; i++) {
- if (book[i] == 0)
- time++;
- }
- printf("%d\n", time);
- system("pause");
- return 0;
- }
法二:
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #pragma warning(disable:4996)
- using namespace std;
- struct stick
- {
- int L;
- int W;
- };
- stick s[5005];
- int n;
- int f[5005] = { 0 };
- bool cmp(stick a, stick b)
- {
- return a.L> b.L;
- }
- int main(){
- scanf("%d", &n);
- int ans = 0;
- for (int i = 1; i <= n; i++)
- scanf("%d%d", &s[i].L, &s[i].W);
- sort(s + 1, s + n + 1, cmp);
- for (int i = 1; i <= n; ++i) {
- if (f[ans] <s[i].W) {
- f[++ans] = s[i].W;
- }
- else {
- int l = 1, r = ans, mid = 0;
- while (l <= r)
- {
- mid = (l + r) / 2;
- if (f[mid]> s[i].W)
- r = mid - 1;
- else
- l = mid + 1;
- }
- f[l] = s[i].W;
- }
- }
- printf("%d", ans);
- system("pause");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3267240.html