题解 P1233 【木棍加工】
Guoyh
2018-12-17 22:32:02
# DP求最大上升子序列
$O(n^2)$ 算法
先根据长度从高到低排序，如果长度相同，再根据宽度从高到低排序。
如果是在同一次准备周期里面，前面的木棍一定在后面木棍之前被加工。
这样，这个问题就转化成了在 $n$ 个数中，求不上升子序列最少个数。
根据 dilworth 定理，不上升子序列最小个数等于最大上升子序列的长度。
于是乎，问题又简化成求 $n$ 个数的最大上升子序列
下面贴代码
```cpp
# include <cstdio>
# include <algorithm>
# define F(i, a, b) for (int i = a; i < b; i++)
using namespace std;
struct MG{
int l, w;
bool operator < (const MG &x) const{ //重定向小于号用于排序
return l == x.l ? w > x.w : l > x.l;
}
} m[5050];
/* //也可以不重定向小于号，定义比较函数
bool cmp(MG x, MG y){
if (x.l != y.l) return x.l > y.l;
else return x.w > y.w;
}
*/
int f[5050]; //dp
int main(){
int n, ans = 0;
scanf("%d", &n);
F(i, 0, n) scanf("%d%d", &m[i].l, &m[i].w);
sort(m, m + n); //根据先前重定向的小于号排序
//sort(m, m + n, cmp) //如果先前定义比较函数要这样写
F(i, 0, n){
for (int j = i - 1; j >= 0; j--){
if (m[i].w > m[j].w) f[i] = max(f[i], f[j] + 1);
}
ans = max(ans, f[i]); //更新ans的值
}
printf("%d\n", ans + 1); //加上最大上升子序列的最后一个元素
return 0;
}
```