题解 P5939 【 [POI1998]折线】

· · 题解

题目传送门

考虑这个45度不是那么好搞，

那么将坐标系逆时针旋转45度，新坐标 (x',y') 满足

x'=x \cos \theta +y \sin \theta,y'=y \cos \theta -x\sin \theta \frac{\sqrt{2}}{2}$ 为了方便可以直接约掉，就题论题就变成了 $(x+y,y-x)

然后排序就是将横坐标作为第一关键字升序排序，

再将纵坐标作为第二关键字降序排序，这样就只用管纵坐标了

那问题就转换成最少用多少个不上升序列可以覆盖所有点

根据Dilworth定理也就是求最长上升子序列的长度

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=30011;
struct rec{int x,y;}a[N]; int n,b[N],len;
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans; 
}
bool cmp(rec a,rec b){return a.x<b.x||(a.x==b.x&&a.y>b.y);} 
signed main(){
    n=iut();
    for (rr int i=1;i<=n;++i){
        rr int x=iut(),y=iut();
        a[i]=(rec){x+y,y-x};
    }
    sort(a+1,a+1+n,cmp);
    b[++len]=a[1].y;
    for (rr int i=2;i<=n;++i){
        if (a[i].y>b[len]) b[++len]=a[i].y;
        else b[lower_bound(b+1,b+1+len,a[i].y)-b]=a[i].y;
    }
    return !printf("%d",len);
}