零件分组
原题链接：（权限限制没有链接）
某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?
输入
第一行为一个整数N（N<=1000），表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。
输出
仅一行，即最少分成的组数。
样例
STICK.IN
5
8 4 3 8 2 3 9 7 3 5
STICK.OUT
2
个人解法：
我可以说我在考场上想到了Dinic求一趟最小链覆盖吗？我已经蒟蒻到了要跑网络流来做最长降子序列的人。
首先我们可以排一趟序（按照某一关键字排序）。比方说我们按照Li排一趟升序。之后我们就等于是在一个Wi里面找不下降子序列的组数。
那么接下来就好写了。求一趟最长降子序列，答案就是最长降子序列的长度。
至于证明？意思是证明最长降子序列的长度为不下降子序列的最少个数。
因为在一个不降序列中入出现了一个比前面元素小的元素，就必须要一个开辟新的不降序列来储存这一个元素。
所以求一趟最长降子序列就可以了。
考场上我居然把最长降子序列打错了！辣鸡样例毁我青春！
代码如下：
var
a,b,tmpa,tmpb:array[0..1000] of longint;//a与b是两个限制条件，tmpa与tmpb是归并排序时两个辅助数组
f:array[0..1000] of longint;//DP数组
n,i,j,ans:longint;
function max(a,b:longint):longint;//取最大值
begin
if a<b then exit(b);
exit(a);
end;
procedure merge(l,m,r:longint);//以a为第一关键字，b为第二关键字归并排序
var
tl,tr,tt:longint;
begin
tl:=l;
tr:=m+1;
tt:=l;
while tt<=r do
if (tr>r) or
((tl<=m) and ((a[tl]<a[tr]) or ((a[tl]=a[tr]) and (b[tl]<b[tr])))) then
begin
tmpa[tt]:=a[tl];
tmpb[tt]:=b[tl];
inc(tl);
inc(tt);
end
else
begin
tmpa[tt]:=a[tr];
tmpb[tt]:=b[tr];
inc(tt);
inc(tr);
end;
for tt:=l to r do
begin
a[tt]:=tmpa[tt];
b[tt]:=tmpb[tt];
end;
end;
procedure sort(l,r:longint);
var
m:longint;
begin
m:=(l+r) shr 1;
if l<m then sort(l,m);
if m+1<r then sort(m+1,r);
merge(l,m,r);
end;
begin
read(n);
for i:=1 to n do//读入
read(a[i],b[i]);
sort(1,n);//排序
b[0]:=maxlongint;
for i:=1 to n do
for j:=0 to i-1 do
if b[j]>b[i] then f[i]:=max(f[i],f[j]+1);//求一趟最长降子序列
for i:=1 to n do
ans:=max(ans,f[i]);//求答案
writeln(ans);//输出
end.
简直了——考场爆零。我已经弱到不行！
DP路上，希望与你们共同进步。