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

128 Replies

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

[cpp]#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;
}
[/cpp]

POJ 2533

[cpp]#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;
}
[/cpp]

128 thoughts 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 *