比赛 |
假期找点事儿做题吧 |
评测结果 |
AAAAAAAAAA |
题目名称 |
渡轮问题 |
最终得分 |
100 |
用户昵称 |
TARDIS |
运行时间 |
0.179 s |
代码语言 |
C++ |
内存使用 |
0.09 MiB |
提交时间 |
2017-06-09 18:51:20 |
显示代码纯文本
#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=10010;
int f[maxn],n,pre[maxn],buf[maxn],ans=-1,goes,lat[maxn];
inline void in(){
#ifdef COGS
freopen("maxxl.in","r",stdin);
freopen("maxxl.out","w",stdout);
#endif
scanf("%d",&n);buf[0]=-1;
for (int i=1;i<=n;i++){
scanf("%d",&buf[i]);
}
}
inline void dp(){
for (int i=n;i>=0;i--){
f[i]=1;
for (int j=n;j>i;j--){
if (buf[i]<=buf[j]){
if (f[i]<f[j]+1){
f[i]=f[j]+1;
lat[i]=j;
}
else if (f[i]==f[j]+1){
if (buf[j]>=buf[lat[i]]){
lat[i]=j;
}
}
}
}
if (ans<=f[i]) ans=f[i],goes=i;
}
}
inline void p(){
printf("%d\n",ans-1);
for (int i=0,j=0;i<=n&&j<=ans-1;i=lat[i],j++){
if (i==0) continue;
printf("%d ",buf[i]);
}
}
int Main(){
in();
dp();
p();
return 0;
}
int main(){;}
int xlm=Main();