[ACM] POJ 1887 2533 解题报告, LIS的nlogn算法..

记录到当前位置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;
}

One thought on “[ACM] POJ 1887 2533 解题报告, LIS的nlogn算法..

  1. viaxl

    #include

    struct BossHP {
    int life,hp;
    };

    int boss[100001];

    BossHP min(BossHP a,BossHP b) {
    if(a.life==b.life)
    return a.hp<b.hp?a:b;
    return a.lifebird) {
    if(!young)
    return a;
    a.hp-=bird;
    return a;
    }
    if(a.hp==bird) {
    a.life–;
    a.hp=boss[a.life];
    return a;
    }
    if(a.hpN)
    M=N;

    for(int i=1;i<=N;i++)
    scanf("%d",bird+i);
    for(int i=1;i<=K;i++)
    scanf("%d",boss+K-i+1);

    for(int i=0;i<=N-M;i++) {
    dp[0][i].life=K;
    dp[0][i].hp=boss[K];
    }

    for(int i=1;i<=M;i++) {
    for(int j=i;j<=N-M+i;j++)
    dp[i][j].life=K+1;
    dp[i][i-1]=dp[i-1][i-1];
    for(int j=i;j=i;j–)
    dp[i][j]=actDouble(dp[i][j-1],bird[i]);
    }

    BossHP result;
    result.life=K+1;
    for(int j=M;j<=N;j++)
    result=min(result,dp[M][j]);
    printf("%d\n",K-result.life);
    }
    return 0;
    }

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.