dp好题--2018.10.16模拟赛T1

本文主要是介绍dp好题--2018.10.16模拟赛T1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
多组数据，先给$t$表示数据组数，给一个$1$到$n$的排列，问是否可以变成一个上升序列和一个下降序列拼起来，并输出上升序列的长度以及这个上升序列，下降序列同理。（语文不太好···
给个样例就是：
输入：
3
5
5 1 4 2 3
5
1 2 3 5 4
1
1
输出：
YES
2 1 2
3 5 4 3
YES
3 1 2 3
2 5 4
YES
0
1 1

数据范围：$t<=50,$ $n<=100000$

solution:
第一眼看到这个数据范围就想到了贪心什么的···
反正差不多是$O(N)$做，也想过$dp$，但感觉用一般的$dp$很不现实
所以就想贪心，但是这个题贪心是错的
真的是$dp$啊我还是太$naive$了

但是要考虑$dp$状态如何设计，果然不是一般的$dp$状态
也不是$lis$不要想多了

设$dp[i]$表示以$i$为上升序列的结尾，最大的下降序列结尾（值）是什么

可以这样设计是因为，已经知道了这个序列一定是由上升和下降序列构成的，所以只要考虑一个的状态，在这个状态下让另一个更优就一定会找到可行解。

然后考虑转移，首先他能$O(n^2)做，$有一个$O(nlogn)$的方法就是线段树优化前缀最大值$emmm$十分暴力很卡常
一个很厉害的$O(n)dp$就是考虑大力分类讨论，$pre[i]$记录上升序列的前一个的下标方便输出，还要记录一个$mv$表示如果$i-1$和$i$不在一个上升序列时前面可以接上$i$的

这么说不太直观还是看代码吧$qwq$

#include<iostream> 
#include<cstdio> 
#include<algorithm> 
#include<cstring> 
#include<cmath> 
#define maxn 100005 
using namespace std; 
int t,n,a[maxn],dp[maxn],pre[maxn]; bool used[maxn]; 
inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}
int main(){freopen("quin.in","r",stdin);freopen("quin.out","w",stdout);t=rd();while(t--){n=rd();for(int i=1;i<=n;i++) a[i]=rd();a[n+1]=n+2; dp[0]=n+1;int mv=0;for(int i=1;i<=n+1;i++){dp[i]=-1;//记得初始化！ if(a[i-1]<a[i]) dp[i]=dp[i-1],pre[i]=i-1;//i和i-1组成上升if(mv!=-1 && a[mv]<a[i] && a[i-1]>dp[i]) dp[i]=a[i-1],pre[i]=mv;//i和mv组成上升if(i!=1 && a[i-1]<a[i]) mv=-1;//重新找上升的结尾 if(dp[i-1]>a[i] && (mv==-1||a[mv]>a[i-1]))mv=i-1;//i可以作为下降的结尾，i-1为上升结尾 }if(dp[n+1]==-1){puts("NO"); continue;}memset(used,0,sizeof used);puts("YES");int u=n+1,tot=0;while(u!=0) used[u]=1,u=pre[u];//找出上升的 for(int i=1;i<=n;i++)if(used[i]) tot++;printf("%d ",tot);for(int i=1;i<=n;i++)if(used[i]) printf("%d ",a[i]);printf("\n%d ",n-tot);for(int i=1;i<=n;i++)if(!used[i]) printf("%d ",a[i]); printf("\n");}return 0;
}

这篇关于dp好题--2018.10.16模拟赛T1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---