[HOJ 86] 接金幣

作法：

首先如果把每個金幣都畫在坐標平面上， x 坐標是時間，y 坐標是位置，那麼就可以發現，如果接了一個金幣 P 之後去接 Q ，那麼 Q 一定會落在一個以 P 為頂點的 1/4 平面的區域裡面，兩條夾線的斜率分別是 1 和 -1 ，所以如果作變換 (x,y) -> (x+y,y-x) 就可以把原題轉換成傳統的問題：給平面上 n 個點，要求找出最少數量的 x , y 坐標都遞增的子數列，使得它們復蓋了這 n 個點，而這就可以用DP做了。

對了， UVa 的11368 在問的就是轉換後的命題。

code :

#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
const int maxn=100000+10 ;
struct P
{
    int x,y ;
    bool operator < (const P &rhs) const
    {
        if(x!=rhs.x) return x<rhs.x ;
        return y<rhs.y ;
    }
}a[maxn];
 
vector<int> dp ;
int ans[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        a[i].x=x+y ; a[i].y=y-x ;
    }
    sort(a+1,a+n+1) ;
    int num=0 ; dp.push_back(INF) ;
    for(int i=1;i<=n;i++)
    {
        int id=lower_bound(dp.begin(),dp.end(),a[i].y,greater<int>())
                -dp.begin() ;
        ans[i]=id ;
        if(id==num+1) num++ , dp.push_back(a[i].y) ;
        else dp[id]=a[i].y ;
    }
    printf("%d\n",num) ;
    for(int i=1;i<=n;i++)
        printf("%d %d %d\n",(a[i].x-a[i].y)/2,(a[i].x+a[i].y)/2,ans[i]);
}