Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51802 AK2022071340 最优子序列 C++ 解答错误 55 172 MS 192792 KB 1848 2022-07-13 14:48:38

Tests(11/20):


#include <bits/stdc++.h> #pragma GCC optimize() using namespace std; char c[3005]; int p[3005]; int f[9005][3005]; int last[26]; int g[9005][3005]; int n,k,type; void pre() { for(int i=1; i<=n; i++) { int num=c[i]-'a'+1; if(!last[num]) continue; if(last[num]==i) p[i]=0; else p[i]=last[num]; last[num]=i; } } int tp[26]; int ts; string get_str(int type,int x,int k) { string ans=""; for(int i=1; i<=k&&x; i++,x=g[type][x]) { while((!((1<<tp[(c[x]-'a'+1)])&type))&&x) x=g[type][x]; ans+=c[x]; } for(int i=0; i<=ans.size()>>1; i++) swap(ans[i],ans[ans.size()-i-1]); return ans; } int main() { scanf("%d%d%d",&n,&k,&type); getchar(); for(int i=1; i<=n; i++) { c[i]=getchar(); int num=c[i]-'a'+1; if(!last[num]) last[num]=i,tp[num]=++ts; } pre(); for(int i=1; i<1<<(ts+1); i++) for(int j=1; j<=n; j++) { int num=tp[c[j]-'a'+1]; if(1<<num&i) { f[i][j]=f[i-(1<<num)][j-1]+1; g[i][j]=j-1; int tmp=f[i][p[j]]+1; if(tmp>f[i][j]) f[i][j]=tmp,g[i][j]=p[j]; /*else { string subs=get_str(i,g[i][j],f[i][j]-1), pres=get_str(i,p[j],tmp-1); if(tmp==f[i][j]&&subs>pres) { g[i][j]=p[j]; } }*/ } else f[i][j]=f[i][j-1],g[i][j]=g[i][j-1]; } int maxn=0,maxi; string ans; int k=(1<<(ts+1))-1; for(int i=1; i<=n; i++) if(f[k][i]>maxn) maxn=f[k][i],ans=get_str(k,i,maxn); /*else if(maxn&&f[k][i]==maxn) { string tmp=get_str(k,i,maxn); if(tmp<ans) ans=tmp; }*/ printf("%d\n",maxn); if(type) printf("%s\n",ans.c_str()); return 0; }


测评信息: