BZOJ 1046: [HAOI2007]上升序列

starli posted @ 2016年5月03日 19:25 in 动态规划 , 268 阅读

n^2的dp可过第一问

第二问只要从左往右贪心的取数就好了 只要当前的数的f[i]>l-top 且大于前一个数 就可以取来

千万要注意 题目中说的字典序最小是下标字典序最小而不是序列的字典序最小!!!!!!!

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=10010;
int f[N],s[N],n,m,q,ans[N],maxdp;
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1046.in","r",stdin);freopen("1046.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(s[i]);s[0]=~0u>>1;
	for(int i=n;i>=1;i--){
		f[i]=1;
		for(int j=i+1;j<=n;j++) if(s[i]<s[j]) f[i]=max(f[i],f[j]+1);
		maxdp=max(maxdp,f[i]);
	}
	read(m);
	while(m--){
		int l;
		read(l);
		if(maxdp>=l){
			int top=0;
			ans[0]=-(~0u>>1);
			for(int i=1;i<=n;i++) if(l-f[i]<=top && s[i]>ans[top]) ans[++top]=s[i];
			for(int i=1;i<l;i++) printf("%d ",ans[i]);printf("%d\n",ans[l]);
		}
		else printf("Impossible\n");
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter