Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51844 AK2022071323 最优子序列 C++ 通过 100 123 MS 114040 KB 2242 2022-07-13 21:00:34

Tests(20/20):


#include <bits/stdc++.h> using namespace std; const int N = 3010,M = (1<<12)+5; int n,k,ty,m,lst[N],nxt[N],dp[N][M][2],vis[N][M][2]; string s,r; struct Node { int x,y; }; void dfs(int x,int y,vector <Node> &t) { if(vis[x][y][0]) return ; vis[x][y][0] = 1; if(dp[x + 1][y][1] == dp[x][y][0] && !vis[x + 1][y][1]) { vis[x + 1][y][1] = 1; t.push_back((Node) { x + 1,y }); } if(dp[x + 1][y][0] == dp[x][y][0]) dfs(x + 1,y,t); } string work(string s) { m = (1 << 12) - 1; memset(dp,0xc0,sizeof(dp)); dp[n][0][0] = 0; for(int i = 0; i < 12; i++) lst[i] = n; for(int i = n - 1; i >= 0; i--) { int c = s[i] - 'a'; nxt[i] = lst[c],lst[c] = i; for(int j = 0; j <= m; j++) { dp[i][j][0] = max(dp[i + 1][j][0],dp[i + 1][j][1]); if(1 & (j >> c)) dp[i][j][1]=max(dp[nxt[i]][j][1],max(dp[i+1][j^(1<<c)][0],dp[i+1][j^(1<<c)][1]))+1; } } int l = 0; string ans = ""; vector <Node> v; for(int i = 0; i <= m; i++) l = max(l,max(dp[0][i][0],dp[0][i][1])); for(int i = 0; i < n; i++) for(int j = 0; j <= m; j++) if(dp[i][j][1] == l) { vis[i][j][1] = 1; v.push_back((Node) { i,j }); } for(int p = l; p >= 1; p--) { vector <Node> t; char ch = 'z'; for(const Node &g : v) ch = min(ch,s[g.x]); ans += ch; int c = ch - 'a'; for(const Node &g : v) { int t1 = g.x,t2 = g.y; if(s[t1] != ch) continue; if(dp[nxt[t1]][t2][1] + 1 == dp[t1][t2][1] && !vis[nxt[t1]][t2][1]) { vis[nxt[t1]][t2][1] = 1; t.push_back((Node) { nxt[t1],t2 }); } if(dp[t1+1][t2^(1<<c)][0] + 1 == dp[t1][t2][1]) dfs(t1+1,t2^(1<<c),t); if(dp[t1+1][t2^(1<<c)][1] + 1 == dp[t1][t2][1] && !vis[t1+1][t2^(1<<c)][1]) { vis[t1+1][t2^(1<<c)][1] = 1; t.push_back((Node) { t1 + 1,t2 ^ (1 << c) }); } } v.swap(t); } return ans; } int main() { cin >> n >> k >> ty; cin >> s; r = work(s); cout << r.length() << endl; if(ty) cout << r << endl; return 0; }


测评信息: