最长上升序列
题目 79 渡轮问题
2013-10-23 08:23:07
|
|
麻煩。。
|
|
为什么只有50分?不是标号字典序最小吗?
#include<iostream> using namespace std; int n; int MAX; int a[10011]; int f[10011]; int p[10011]; int ans[10011],l; int main() { freopen("maxxl.in","r",stdin); freopen("maxxl.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); MAX=-1; int k; for(int i=1;i<=n;++i){ f[i]=1; p[i]=i; for(int j=1;j<=i-1;++j) if(a[i]>a[j]&&f[i]<f[j]+1){ f[i]=f[j]+1; p[i]=j; } if(f[i]>MAX){ MAX=f[i]; k=i; } } printf("%d\n",MAX); l=0; while(k!=p[k]){ ans[++l]=a[k]; k=p[k]; } ans[++l]=a[k]; for(int i=MAX;i>1;--i) printf("%d ",ans[i]); printf("%d\n",ans[1]); return 0; } |