[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算法..”

Leave a Reply

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