题意：有n条木棒，给出它们每条的l和w，用一台机器对它们进行加工，如果机器正加工的木条，与在它之前加工的木块有关系：l <= l'和w <= w'，则机器不用准备时间，否则需准备1分钟。问加工完全部木棒，机器最少需要准备多久。
思路：每次以某一点为起点，向后贪心地走。（虽然是求小链覆盖，但是不用上网络流）
或者利用diworth定理，最长反链 = 最小链覆盖（本题的最长反链就是最长下降子序列）
#include <cstdio> #include <utility> #include <vector> #include <algorithm> using namespace std; typedef pair<int,int> pii; const int maxn =5005; vector<pii> ve; int vis[maxn]; int main(){ int T; scanf("%d",&T); while(T--){ ve.clear(); int n;scanf("%d",&n); for( int i = 0 ;i <= n;i++ ) vis[i] = 0; for( int w,h,i = 1;i <= n;i++ ){ scanf("%d%d",&w,&h); ve.push_back( pii(w,h) ); } sort( ve.begin(),ve.end() ); int ans = 0; for( int i = 0;i < n;i++ ){ if( vis[i] ) continue; vis[i] = 1;ans++; int mx = ve[i].second; for( int j = i+1;j < n;j++ ){ if(vis[j]) continue; if( ve[j].second >= mx ){ mx = ve[j].second; vis[j] = 1; } } } printf("%d\n",ans); } return 0; }
