首页 > 代码库 > UESTC 电子科大专题训练 DP-G
UESTC 电子科大专题训练 DP-G
UESTC 1006
题意:找出LIS并输出其中字典序最小的一个序列
思路:一开始的想法是找出LIS用dp[i]保存以ai为结尾的LIS,然后从后面往前每次找出每一位的最小值,然后想了一下觉得不行,因为可能找到第k位的最小的位置p之后,第k-1位的最小值可能在p的后面,这样就导致找不到最小的字典序,但其实这种情况是不存在的,因为由LIS的性质(s[i]<s[i+1]) ,可以知道,如果dp[i] = dp[j] && i<j --->一定可以推得a[i]>=a[j] ,因为如果a[i]<a[j] 那么意味着a[i]到a[j]也可以形成一个上升序列,那么必然得不到 dp[i]=dp[j]的前提,所以可知,dp[i]相等的前提下ai最小的一定在最后面,所以只需要从最后面往前依次取最靠右的且dp值依次为 cnt-->1 就可以了,由于开始没有想到这个结论,所以我用另一种方法写的,存2个数组,dp1 dp2,dp1[i]的意义如上述,dp2[i]表示以i为开始的LIS,那么可以得到,dp1[i]+dp2[i]-1的值便是ai所在的上升序列的最大长度,如果结果等于cnt说明ai是其中某个LIS的第dp1[i]位,遍历找出每一位的最小即可,这里把2种方法的代码都贴上来
AC代码:
1
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e5+100; const ll mod=1e9+7; int dp1[1005]; int main(){ int T; cin>>T; while(T--){ mem(c),mem(dp1); cin>>n>>a[1]; c[0]=-inf,c[1]=a[1],dp1[1]=1,cnt=0; for(int i=2; i<=n; ++i){ cin>>a[i];c[i]=inf; int l=0,r=i-1,ans=0; while(l<=r){ int mid=l+r>>1; if(c[mid]<a[i]){ ans=mid; l=mid+1; } else r=mid-1; } dp1[i]=ans+1; cnt=max(cnt,ans+1); c[ans+1]=min(c[ans+1],a[i]); } cout<<cnt<<" "; int ct[N],p=cnt;mem(ct); for(int i=n; i>=1; --i){ if(dp1[i]==p){ ct[p]=a[i]; p--; } } for(int i=1; i<=cnt; ++i){ cout<<ct[i]<<" "; } cout<<"\n"; } return 0; }
2
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e5+100; const ll mod=1e9+7; int a[1005],c[1005],dp1[1005],dp2[1005],n,cnt; int main(){ //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ mem(c),mem(dp1),mem(dp2); cin>>n>>a[1]; c[0]=-inf,c[1]=a[1],dp1[1]=1,cnt=0; for(int i=2; i<=n; ++i){ cin>>a[i];c[i]=inf; int l=0,r=i-1,ans=0; while(l<=r){ int mid=l+r>>1; if(c[mid]<a[i]){ ans=mid; l=mid+1; } else r=mid-1; } dp1[i]=ans+1; cnt=max(cnt,dp1[i]); c[ans+1]=min(c[ans+1],a[i]); } dp2[n]=1; for(int i=n-1; i>=1; --i){ dp2[i]=1; for(int j=i+1; j<=n; ++j){ if(a[j]>a[i]){ dp2[i]=max(dp2[i],dp2[j]+1); } } } int ct[1005]; memset(ct,63,sizeof(ct)); for(int i=1; i<=n; ++i){ if(dp1[i]+dp2[i]==cnt+1){ ct[dp1[i]]=min(ct[dp1[i]],a[i]); } } cout<<cnt<<" "; for(int i=1; i<=cnt; ++i){ cout<<ct[i]<<" "; } cout<<endl; } return 0; }
UESTC 电子科大专题训练 DP-G
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。