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; }
总结
dilworth定理：不下降子序列最小个数等于最大上升子序列的长度
