记录到当前位置combo数为k的尾巴的最小值, 比如 1 3 2 6, 则 dp[combo]=tail 罗列为 dp[1]=1, dp[2]=2 (1,2的尾巴比1,3等小), dp[3]=6, combo最大为6. 然后再多加一位就看能不能更新前面combo数对应的tail, 让tail更小; 当然还看combo数能不能+1. 比如1 3 2 6再加个5, dp[3]就=5 (1,2,5的tail比1,2,6的tail小), 不加5加7就多一个dp[4]=7. 因为dp[combo]值相对于combo数是递增的, 所以可以二分查找实现nlogn.

这两个是买一送一的题目.. 1887的二分写的有点蛋疼.. 2533要求不能相等, 就加了个标记每次对二分的两个指针p0,p1, 和中点(p0+p1)/2看一下, 重复就continue, 不重复一样做, 省得麻烦.. 想了一下还可以前面严格<, 后面可以>=, 这样更新tail的时候就不会重复产生影响.

代码点下面:

POJ 1883

#include <stdio.h>

int main() {
    int a[5000];
    int e[5000],N=0;
    int nextline;
    scanf("%d",&nextline);
    while(nextline!=-1) {
        N++;
        int an=0;
        while(nextline!=-1) {
            an++;
            a[an]=nextline;
            scanf("%d",&nextline);
        }

        //DP it.
        int en=0;
        e[0]=0;
        for(int i=an;i>=1;i--) {
            int foo=0;
            int p0=1,p1=en;
            e[en+1]=0x7fffffff;
            while(1) {
                int p=(p1+p0)/2;
                if(a[i]>=e[p] && a[i]<e[p+1]) {
                    p1=p0=p;
                    break;
                }
                if(a[i]<e[p])
                    p1=p-1;
                if(a[i]>=e[p+1])
                    p0=p+1;
            }
            if(p0==en) {
                en++;
                e[en]=a[i];
            }
            else
                e[p1+1]=a[i];
        }

        printf("Test #%d:\n  maximum possible interceptions: %d\n\n",N,en);

        scanf("%d",&nextline);
    }
    return 0;
}

POJ 2533

#include <stdio.h>

int main() {
    int a[1005];
    int e[1005];
    int an;
    scanf("%d",&an);
    for(int i=1;i<=an;i++)
        scanf("%d",a+i);

    //DP it.
    int en=0;
    e[0]=0x80000000;
    for(int i=1;i<=an;i++) {
        int foo=0;
        int p0=1,p1=en;
        e[en+1]=0x7fffffff;
        bool flag=true;
        while(1) {
            int p=(p1+p0)/2;
            if(e[p0]==a[i] || e[p1]==a[i] || e[p]==a[i]) {
                flag=false;
                break;
            }
            if(a[i]>=e[p] && a[i]<e[p+1]) {
                p1=p0=p;
                break;
            }
            if(a[i]<e[p])
                p1=p-1;
            if(a[i]>=e[p+1])
                p0=p+1;
        }
        if(!flag)
            continue;
        if(p0==en) {
            en++;
            e[en]=a[i];
        }
        else
            e[p1+1]=a[i];
    }

    printf("%d\n",en>0?en:1);
    return 0;
}