有\(N\)根木棍，每根的长度\(L\)和重量\(W\)已知。这些木棍将被一台机器一根一根地加工。机器需要一些启动时间来做准备工作，启动时间与木棍被加工的具体情况有关。启动时间遵循以下规则：
- 加工第一根木棍的启动时间为1分钟。
- 加工完长度为\(L_i\)，重量为\(W_i\)的木棍后，紧跟着加工长度为\(L_i+1\)，重量为\(W_i+1\)的木棍时，若\(L_i\le L_i+1\)且\(W_i\le W_i+1\)，则加工木棍\(i+1\)时，不需要启动时间。例如：有\(5\)根木棍，它们的长度和重量为\((9,4),(2,5),(1,2),(5,3),(4,1)\)，则最小总启动时间为2分钟（加工序列为\((4,1),(5,3),(9,4),(1,2),(2,5)\)）。
输入:
第一行一个整数\(n(1\le n\le 5000)\)，表示木棍的数量。第二行\(2n\)个整数，\(l_1,w_1,l_2,w_2,cdots,l_n,w_n(1\le l_i,w_i\le 10000)\)，为各根木棍的长度和重量，这\(2n\)个整数以若干个空格分隔。
输出:
一行: 一个整数，即最小总启动时间。
样例输入1
样例输出1
样例输入2
样例输出2
题解
我对这题的第一反应是DAG，于是建了一张图，发现对任意一个点往那边跑都没关系，如下图（图中1到所有点都要连一条边，但忘画了怕图太乱了，就没有连）：
对于点1来说，往2还是往3是无关的：因为如果选2则3要跑一遍，选3则2要在跑一遍，两者结果是相同的。但是选4是不可行的，因为选2的方案更佳。
于是我们想到用一个pair（我用了结构体），然后进行排序，对于每一个没有标记过的点直接往后找，第一个能连边的一定符合要求（否则在此之前一定有一个可以连边的点）。
复杂度\(O(n^2)\)，听说可以用LIS的方法优化到\(O(n\log n)\)。
代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 5005;
struct akking
{
int l, w;
inline bool operator < (const akking& other) const
{
return l < other.l || (l == other.l && w < other.w);
}
} sxd[maxn];
bool vis[maxn];
int n;
int main()
{
freopen("wooden.in", "r", stdin);
freopen("wooden.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d%d", &sxd[i].l, &sxd[i].w);
sort(sxd+1, sxd+n+1);
int ans = 0;
for(int i = 1; i <= n; ++i)
{
if(!vis[i])
{
ans++;
for(int j = i+1; j <= n; ++j)
{
if(!vis[j] && sxd[i].l <= sxd[j].l && sxd[i].w <= sxd[j].w)
{
vis[j] = true;
sxd[i] = sxd[j];
}
}
}
}
printf("%d", ans);
fclose(stdin);
fclose(stdout);
return 0;
}