[TIOJ 1316] 晶片設計 Chips

作法：

題目簡單來說就是，有 n 條兩兩端點不重複的線段，要選出最多條使得沒有三條線段同時覆蓋一個點(端點也算)。如果問題的三改成二，也就是任兩條線段不交，那就可以先把有包含別人的線段都砍掉(顯然選他們不會比選裡面的線段好)，然後再從左到右 greedy 就好了。但這裡沒辦法這樣作，有包住別人的線段不一定沒用。

如果把問題反過來，考慮先把全部的線段都取過來，這時候有些點被 > 2 條線段覆蓋了，必須要把一些線段移除掉。而這個問題就可以用貪心解決了，首先看最左邊的不合法的點，那麼可以知道我們只要移除「左端點 <= 他且右端點衝得最遠」的線段，這會是最好的選擇，所以答案就是 n - 移除線段的數量。

這裡實作上應該可以到 O(nlogn)，維護還剩哪些線段之類的，不過因為 n 小小的所以我直接寫了 O(n^2) 的作法。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=8000+10 ;
 
int a[maxn] ;
int l[maxn],r[maxn],num[maxn] ;
bool used[maxn] ;
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=2*n;i++)
    {
        scanf("%d",&a[i]) ;
        if(!l[a[i]]) l[a[i]]=i ;
        else r[a[i]]=i ;
    }
 
    int now=2 ;
    for(int i=1;i<=2*n;i++)
    {
        if(i==l[a[i]]) now-- ;
        num[i]=now ;
        if(i==r[a[i]]) now++ ;
    }
 
    int ans=n ;
    for(int i=1;i<=2*n;i++) while(num[i]<0)
    {
        int M=0 , id ;
        for(int j=1;j<=i;j++)
            if(!used[a[j]] && j==l[a[j]] && r[a[j]]>M)
            M=r[id=a[j]] ;
        used[id]=1 ;
        for(int j=l[id];j<=r[id];j++) num[j]++ ;
        ans-- ;
    }
    printf("%d\n",ans) ;
}