首页 > 代码库 > 序列DP(输出有要求)
序列DP(输出有要求)
DP
Time Limit:10000MS Memory Limit:165888KB 64bit IO Format:%lld & %lluDescription
对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax
2 < … < axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。任务给
出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先
x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.
Input
第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。下面接M
行每行一个数L，表示要询问长度为L的上升序列。N<=10000，M<=1000
Output
对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.
Sample Input
63 4 1 2 3 63645Sample Output
Impossible1 2 3 6Impossible
//序列DP题，DP是真的要思维。。。一定要想到最佳的DP方法，一般DP方法能做出来还是TLE了
这里 DP[i] 代表序列以第 i 个元素为开头的上升序列的可达的最大长度，然后，做过序列DP的应该都会做了
从后向前转移状态 DP[i] = max ( DP[i] , DP[j] + 1 ) num[i] < num [j] && i < j
1 #include <stdio.h> 2 3 #define INF 1000000000 4 int num[10005];//数据 5 int dp[10005];//记录到这最大上升长度 6 int ans[10005];//存储答案的 7 int n,m; 8 9 void Init()10 {11 scanf("%d",&n);12 int i,j;13 for (i=1;i<=n;i++)14 scanf("%d",&num[i]);15 for (i=n;i>=1;i--)16 {17 dp[i]=1;18 for (j=i+1;j<=n;j++)19 {20 if (num[j]>num[i]&&dp[j]+1>dp[i])21 {22 dp[i]=dp[j]+1;23 }24 }25 }26 }27 28 int main()29 {30 Init();31 scanf("%d",&m);32 while (m--)33 {34 int i,j,l,ok=0;35 scanf("%d",&l);36 37 int pos;38 for (i=1;i<=n;i++)39 {40 if (ok==0&&dp[i]>=l)41 {42 int tmp=1;43 ans[1]=num[i];44 if (tmp==l)45 {46 ok=1;47 break;48 }49 int pre=i;50 for (j=i+1;j<=n;j++)51 {52 if (num[j]>num[pre]&&dp[j]>=l-tmp)53 {54 ans[++tmp]=num[j];55 pre=j;56 if (tmp==l)57 {58 ok=1;59 break;60 }61 }62 }63 }64 }65 if (ok==0)66 printf("Impossible\n");67 else68 {69 for (i=1;i<l;i++)70 printf("%d ",ans[i]);71 printf("%d\n",ans[l]);72 }73 74 }75 return 0;76 }
序列DP(输出有要求)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。