记录编号	203853	评测结果	AAAAAAAAAA
题目名称	渡轮问题	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.184 s
提交时间	2015-11-03 18:48:50	内存使用	0.41 MiB

#include<cstdio>
int EPX,n,ans,w[11000],f[11000],pre[11000];
inline void in(int &TEMP)
{
	for(TEMP=getchar();TEMP<48||TEMP>57;TEMP=getchar());
	TEMP^=48;
	for(EPX=getchar();EPX<58&&EPX>47;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+(EPX^48);
}
int main()
{
	freopen("maxxl.in","r",stdin);
	freopen("maxxl.out","w",stdout);
	in(n);
	for(int i=1;i<=n;++i)
		in(w[i]);
	for(int i=n;i;--i)
	{
		for(int j=n;j>i;--j)
		    if(w[i]<=w[j]&&f[i]<=f[j]+1)
		    {
				f[i]=f[j]+1;
				pre[i]=j;
		    }
		if(f[ans]<=f[i])
		    ans=i;
	}
	printf("%d\n%d ",f[ans]+1,w[ans]);
	while(pre[ans])
	{
		printf("%d ",w[pre[ans]]);
		ans=pre[ans];
	}
	//while(1);
}
/*
#include<cstdio>
int EPX,n,ans,w[11000],f[11000],pre[11000];
inline void in(int &TEMP)
{
	for(TEMP=getchar();TEMP<48||TEMP>57;TEMP=getchar());
	TEMP^=48;
	for(EPX=getchar();EPX<58&&EPX>47;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+(EPX^48);
}
int main()
{
	freopen("maxxl.in","r",stdin);
	freopen("maxxl.out","w",stdout);
	in(n);
	for(int i=1;i<=n;++i)
		in(w[i]);
	for(int i=n;i;--i)
	{
		for(int j=n;j>i;--j)
		{
			if(w[i]<w[j]&&f[i]==f[j]+1&&w[pre[i]]>w[j])
			    pre[i]=j;
		    if(w[i]<w[j]&&f[i]<f[j]+1)
		    {
				f[i]=f[j]+1;
				pre[i]=j;
		    }
		}
		if(f[ans]==f[i]&&w[i]<w[ans])
		    ans=i;
		if(f[ans]<f[i])
		    ans=i;
	}
	printf("%d\n%d ",f[ans]+1,w[ans]);
	while(pre[ans])
	{
		printf("%d ",w[pre[ans]]);
		ans=pre[ans];
	}
	while(1);
}
这题的难点是字典序！输出方案很恶心！
以此练手！
上个程序是废的！
题目中说以标号的字典序输出！
还有就是：最长不下降子序列！
*/