首页 > 代码库 > poj 2127 lcis wa

poj 2127 lcis wa

#include<iostream>#include<cstdio>#include<stack>#include<algorithm>#include<cstring>using namespace std;typedef long long ll;const int maxn = 505;const ll one = 1;const ll inf = one << 32;ll n1, n2, a[maxn], b[maxn];ll l[maxn][maxn];struct xx{    int i, j;}pre[maxn][maxn], ind[maxn];int insert_(ll *la, int p, int i, int j, ll e){    while(la[p] < e) p++;    la[p]=e;    ind[p]=(xx){i, j};    if(p) pre[i][j]=ind[p-1];    return p;}void lcis(){    int i, j, x, p=0;    for(i=0; i<n2; i++)        fill_n(l[i], n2, inf);    memset(pre, -1, sizeof(pre));    for(i=0; i<n1; i++){        x=-1, p=0;        for(j=0; j<n2; j++){            if(a[i]==b[j]) x=p=insert_(l[j], p, i, j, a[i]);            else{                if(x!=-1 && l[j][x]>l[j-1][x]) l[j][x]=l[j-1][x];                else x=-1;            }        }    }}void print(){    int t, j, i;    for(j=n2-1; j>-1; j--) if(l[n2-1][j]!=inf)        break;    stack<ll> s;    printf("%d\n", j+1);    i = ind[j].i;   j=ind[j].j;    while(i > -1){        s.push(a[i]);        t=pre[i][j].i;  j=pre[i][j].j;        i=t;    }    while(!s.empty()){        printf("%lld", s.top());  s.pop();        printf("%c", s.empty()?‘\n‘:‘ ‘);    }}int main(){    while(scanf(" %lld", &n1)==1){        for(int i=0; i<n1; i++) scanf(" %lld", a+i);        scanf(" %lld", &n2);        for(int i=0; i<n2; i++) scanf(" %lld", b+i);        lcis();        print();    }    return 0;}

 to be continued;