Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51608 AK2022071326 最优子序列 C++ 解答错误 45 1000 MS 164060 KB 1372 2022-07-13 12:09:25

Tests(9/20):


#include<bits/stdc++.h> using namespace std; long long ans,n,k,type,cnt; long long dp[3010][4100];//i为结尾的最长子序列 string a; char ch[3010]; int b[20],c[3010]; int ste; int ansl[3010],ansll[3010]; void dfs(long long x,long long check,long long sum,int step) { //cout<<x; if(sum<=dp[x][check]){ return ; } ansl[step]=x; // cout<<x<<check<<" "<<sum<<endl; dp[x][check]=sum; if(x==cnt) { //cout<<sum; if(ans<sum) { ans=sum; ste=step; for(int i=1;i<=step;i++) { ansll[i]=ansl[i]; // for(int j=1;j<=c[ansll[i]];j++) cout<<ch[ansll[i]]; } // cout<<endl; } return ; } for(int i=x+1;i<=cnt;i++) { //cout<<x<<i<<endl; if(ch[x]==ch[i]) { dfs(i,check,sum+c[i],step+1); } else { if(check&(1<<(ch[i]-'a'))) continue; dfs(i,check+(1<<(ch[i]-'a')),sum+c[i],step+1); } } } int main() { cin>>n>>k>>type; cin>>a; a=' '+a; for(int i=1;i<=n;i++) { cnt++; while(a[i]==a[i+1]) { c[cnt]++; i++; } c[cnt]++; if(!b[a[i]-'a'+1]) b[a[i]-'a'+1]=cnt; ch[cnt]=a[i]; //cout<<i<<endl; } for(int i=1;i<=14;i++) if(b[i]) dfs(b[i],1<<(ch[b[i]]-'a'),c[b[i]],1); cout<<ans<<endl; if(type==0) return 0; for(int i=1;i<=ste;i++) { for(int j=1;j<=c[ansll[i]];j++) cout<<ch[ansll[i]]; } cout<<endl; return 0; }


测评信息: