比赛 假期找点事儿做题吧 评测结果 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();