提交时间:2022-07-13 15:13:17
运行 ID: 51820
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=3005; int n,k,type,ans,top; int dp[N][4500][2],lst[13]; pair<int,int>pre[N][4500][2]; char s[N],a[N],b[N]; void cmp(int a1,int w1,int k1,int a2,int w2,int k2,int val,pair<int,int> l) { if(dp[a2][w2][k2]+val==dp[a1][w1][k1]&&s[l.first]<s[pre[a1][w1][k1].first]) pre[a1][w1][k1]=l; else if(dp[a2][w2][k2]+val>dp[a1][w1][k1]) dp[a1][w1][k1]=dp[a2][w2][k2]+val,pre[a1][w1][k1]=l; } int main() { // freopen("seq.in","r",stdin); // freopen("seq.out","w",stdout); scanf("%d%d%d",&n,&k,&type); scanf("%s",s+1); reverse(s+1,s+1+n); for(int i=1; i<=n; i++) { for(int w=0; w<(1<<k); w++) { if(w&(1<<(s[i]-'a'))) cmp(i,w,1,lst[s[i]-'a'],w,1,1,make_pair(lst[s[i]-'a'],w)); else { cmp(i,w|(1<<(s[i]-'a')),1,i-1,w,0,1,pre[i-1][w][0]); cmp(i,w|(1<<(s[i]-'a')),1,i-1,w,1,1,make_pair(i-1,w)); } cmp(i,w,0,i-1,w,0,0,pre[i-1][w][0]); cmp(i,w,0,i-1,w,1,0,make_pair(i-1,w)); } lst[s[i]-'a']=i; } for(int i=1; i<=n; i++) for(int w=0; w<(1<<k); w++) ans=max(ans,dp[i][w][1]); printf("%d\n",ans); if(type) { for(int i=1;i<=n;i++) for(int w=0;w<(1<<k);w++) if(dp[i][w][1]==ans) { int x=i,y=w,p,q,flag=0; top=0; while(x) { if(!a[top+1]||(a[top+1]>s[x])) flag=1; if(!flag&&a[top+1]&&a[top+1]<s[x]) break; b[++top]=s[x]; if(flag) a[top]=s[x]; p=pre[x][y][1].first;q=pre[x][y][1].second; x=p;y=q; } } for(int i=1;i<=ans;i++) printf("%c",a[i]); } return 0; }