Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51670 UhhhQQQU 最优子序列 C++ 解答错误 0 0 MS 844 KB 3123 2022-07-13 12:30:25

Tests(0/20):


#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int N=3e3+10; int n,K,tp; int f[2][(1<<13)+1][2][15]; int cnt[(1<<13)+1]; char ch[N]; int a[N]; struct Elysia{ int num,cnt; }d[(1<<13)+1]; bool cmp(Elysia x,Elysia y) { return x.cnt<y.cnt; } bool app[N][15]; int main() { scanf("%d %d %d",&n,&K,&tp); int tpp=(1<<K); scanf("%s",ch+1); for(int i=1;i<=n;i++) { a[i]=(int)(ch[i]-'a'+1); for(int j=1;j<=12;j++) app[i][j]=app[i-1][j]; app[i][a[i]]=1; } int p=0,nxt; for(int i=0;i<tpp;i++) d[i].cnt=d[i>>1].cnt+(i&1),d[i].num=i; sort(d,d+tpp,cmp); // for(int i=0;i<=n;i++) // { // nxt=p^1; // for(int s=0;s<tpp;s++) // { // if(d[s].cnt>i) // break; // if(f[nxt][s][0][a[i]]<f[p][s][1][a[i]]) // f[nxt][s][0][a[i]]=f[p][s][1][a[i]]; //// else if(f[nxt][s][0][a[i]]==f[p][s][1][a[i]]&&ss[nxt][s][0][a[i]]>ss[p][s][1][a[i]]) //// ss[nxt][s][0][a[i]]=ss[p][s][1][a[i]]; // if(!(s&(1<<a[i+1]-1))) // { // if(a[i+1]!=a[i]) // { // if(f[nxt][s|(1<<a[i]-1)][1][a[i+1]]<f[p][s][1][a[i]]+1) // f[nxt][s|(1<<a[i]-1)][1][a[i+1]]=f[p][s][1][a[i]]+1; //// else if(f[nxt][s|(1<<a[i]-1)][1][a[i+1]]==f[p][s][1][a[i]]+1&&ss[nxt][s|(1<<a[i]-1)][1][a[i+1]]>ss[p][s][1][a[i]]+ch[i+1]) //// ss[nxt][s|(1<<a[i]-1)][1][a[i+1]]=ss[p][s][1][a[i]]+ch[i+1]; // } // else // { // if(f[nxt][s][1][a[i+1]]<f[p][s][1][a[i]]+1) // f[nxt][s][1][a[i+1]]=f[p][s][1][a[i]]+1; //// else if(f[nxt][s][1][a[i+1]]==f[p][s][1][a[i]]+1&&ss[nxt][s][1][a[i+1]]>ss[p][s][1][a[i]]+ch[i+1]) //// ss[nxt][s][1][a[i+1]]=ss[p][s][1][a[i]]+ch[i+1]; // } // } // for(int j=1;j<=12;j++) // { // if((s&(1<<j-1))&&app[i][j]) // continue; // if(f[nxt][s][0][j]<f[p][s][0][j]) // f[nxt][s][0][j]=f[p][s][0][j]; //// else if(f[nxt][s][0][j]==f[p][s][0][j]&&ss[nxt][s][0][j]>ss[p][s][0][j]) //// ss[nxt][s][0][j]=ss[p][s][0][j]; // if(!(s&(1<<a[i+1]-1))) // { // if(a[i+1]==j) // { // if(f[nxt][s][1][a[i+1]]<f[p][s][0][j]+1) // f[nxt][s][1][a[i+1]]=f[p][s][0][j]+1; //// else if(f[nxt][s][1][a[i+1]]==f[p][s][0][j]&&ss[nxt][s][1][a[i+1]]>ss[p][s][0][j]+ch[i+1]) //// ss[nxt][s][1][a[i+1]]=ss[p][s][0][j]+ch[i+1]; // } // else // { // if(f[nxt][s|(1<<j-1)][1][a[i+1]]<f[p][s][0][j]+1) // f[nxt][s|(1<<j-1)][1][a[i+1]]=f[p][s][0][j]+1; //// else if(f[nxt][s|(1<<j-1)][1][a[i+1]]==f[p][s][0][j]+1&&ss[nxt][s|(1<<j-1)][1][a[i+1]]>ss[p][s][0][j]+ch[i+1]) //// ss[nxt][s|(1<<j-1)][1][a[i+1]]=ss[p][s][0][j]+ch[i+1]; // } // } // } // } // p^=1; // } int ans=0; for(int s=0;s<tpp;s++) for(int j=1;j<=12;j++) { if(f[p^1][s][0][j]>ans) ans=f[p^1][s][0][j]; // else if(f[p^1][s][0][j]==ans&&rans>ss[p^1][s][0][j]) // rans=ss[p^1][s][0][j]; if(f[p^1][s][1][j]>ans) ans=f[p^1][s][1][j]; // else if(ans==f[p^1][s][1][j]&&rans>ss[p^1][s][1][j]) // rans=ss[p^1][s][1][j]; } printf("%d\n",ans); return 0; }


测评信息: