[TIOJ 1472][ZJ b178] 遊輪 Boat

作法：

這題用到了偏序集的 Dilworth 定理，之前在選訓不知道為什麼根余紅勳、趙庭偉研究了好久那些東西，沒想到資訊竟然會出現這個XD

如果考慮建一張圖，頂點是那些船，並且如果兩艘船可以停在同一個碼頭就在他們之間連邊，那麼問題就變成我們要用最少的完全圖來覆蓋所有的頂點。而到這裡其實可以猜說答案就是在圖裡「兩兩沒有連邊的頂點子集合的最大個數」。所以只要對每條線段，看有哪些線段的左端點在他的左端點右邊，且和他不能在同一個碼頭，然後把這些線段 sort ( x 從小到大，一樣時 y 從大到小 ) ，求 y 坐標的 LIS 長度就好了。

至於這件事為什麼是對的，考慮一個偏序集( 嚴謹定義可參考維基 )，他的元素是這些線段們，並且如果兩條線段有包含或是不相交的情形，就在他們之間定義小於，定法是先比左端點大小再比右端點大小，而如果兩條線段不是上面的情形(也就代表他們不能用同一個碼頭)，那就讓他們沒辦法比大小。並且可以知道這樣定會滿足若 a>b , b>c ，則 a>c ，所以這樣定是沒問題的。這樣題目就變成要用最少條鍊( chain ) ( 滿足其內部的元素兩兩可比大小 )去覆蓋這個偏序集的所有元素，而 Dilworth 定理說他的數量恰等於最大反鍊( antichain )( 滿足其內部的元素兩兩不可比大小 )的大小，就得證了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10 ;
 
struct P
{
    int x,y ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ? y>rhs.y : x<rhs.x ;
    }
}a[maxn],b[maxn];
 
vector<int> v ;
int dp[maxn] ;
int LIS()
{
    int num=0 ;
    dp[0]=0 ;
    for(auto i : v)
    {
        int id=lower_bound(dp,dp+num+1,i)-dp ;
        dp[id]=i ;
        if(id==num+1) num++ ;
    }
    return num ;
}
 
int solve(int num)
{
    sort(b,b+num) ;
    v.clear() ;
    for(int i=0;i<num;i++) v.push_back(b[i].y) ;
    return LIS() ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y) ;
    int ans=0 ;
    for(int i=1;i<=n;i++)
    {
        int cnt=0 ;
        b[cnt++]=a[i] ;
        for(int j=1;j<=n;j++) if(i!=j)
        {
            if(a[i].x>=a[j].x) continue ;
            if(a[j].y<=a[i].y) continue ;
            if(a[j].x>a[i].y) continue ;
            b[cnt++]=a[j] ;
        }
        ans=max(ans,solve(cnt)) ;
    }
    printf("%d\n",ans) ;
}