首页 > 代码库 > 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;
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。