[HOJ 134][POI 14 Stage 3] Driving Exam

作法：

首先發現如果能夠從最底下走到1和n這兩個終點的話就能走到1~n所有終點了。
把走的過程整個反過來，邊也全部反向，改成從上面走到下面，這樣問題就變成：加上 k 條邊使得「最左上角的點能走到的點集」交集「最左上角的點能走到的點集」的個數最多。

想法是：往左往右的邊分開處理，如果能知道最左上角的點在加上 x 條往右的邊之後，最遠可以走到哪個最底下的點(右上角類似)的話，就可以枚舉新增的往右的邊的個數並求答案的最大值。

再來以左上角的點為例，現在想求他在加上 i 條往右的邊之後最遠可以走到哪，不如反過來求如果想要走到第 i 條，那麼至少要新增幾條向右的邊。再注意到：如果稱原本的圖裡就有的(東西向)邊為「實邊」，剩下的為「虛邊」，設從左上角(沿實邊或虛邊)走到第 i 行的最多經過的實邊數目 = x ，那麼想要走到第 i 條的至少要新增的邊數就 = i - 1 - x 。於是就可以用DP作最大實邊數目，作法和LIS類似。

另外原題是問最多能夠「增加」幾個能到達1~n的點，所以要扣掉原本的。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
int n,m ;
int dp[maxn] ;
void solve(vector<int> v[],int *mi)
{
    mi[1]=0 ;
    int num=0 ; dp[0]=0 ;
    for(int i=2;i<=n;i++)
    {
        for(int j=((int)v[i].size())-1;j>=0;j--)
        {
            int id=upper_bound(dp,dp+num+1,v[i][j])-dp ;
            dp[id]= (id==num+1 ? v[i][j] : min(dp[id],v[i][j])) ;
            if(id==num+1) num++ ;
        }
        mi[i]=i-1-num ;
    }
}
 
vector<int> v1[maxn],v2[maxn] ;
int a[maxn],b[maxn] ;
main()
{
    int p,k ; scanf("%d%d%d%d",&n,&m,&p,&k) ;
    while(p--)
    {
        int x,y,type ; scanf("%d%d%d",&x,&y,&type) ;
        if(type==1) v1[x+1].push_back(m-y) ;
        else v2[n-x+1].push_back(m-y) ;
    }
    for(int i=2;i<=n;i++)
    {
        sort(v1[i].begin(),v1[i].end()) ;
        sort(v2[i].begin(),v2[i].end()) ;
        v1[i].resize(unique(v1[i].begin(),v1[i].end())-v1[i].begin()) ;
        v2[i].resize(unique(v2[i].begin(),v2[i].end())-v2[i].begin()) ;
    }
    solve(v1,a) ;
    solve(v2,b) ;
 
    int i=1,j=1,ans1=0 ;
    for(int z=0;z<=k;z++)
    {
        while(i<=n && a[i]<=z) i++ ; i-- ;
        while(j<=n && b[n-j+1]>k-z) j++ ;
        ans1=max(ans1,i-j+1) ;
    }
 
    i=n ; j=1 ;
    while(a[i]) i-- ;
    while(b[n+1-j]) j++ ;
    int ans2=max(0,i-j+1) ;
 
    printf("%d\n",ans1-ans2) ;
}