Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
51586 | Scorpio | 最优子序列 | C++ | 运行出错 | 0 | 0 MS | 244 KB | 1768 | 2022-07-13 11:54:18 |
#include<bits/stdc++.h> using namespace std; const int maxn = 3005; const int maxk = 14; struct Node{ int l, r, len; char letter; }; Node shorten[maxn]; bool appeared[maxk], exsit[maxn]; char lett[maxn]; char lst; int n, k, type, alb, R, L, ans, flg, cnt; bool cmp(Node a, Node b){ if(a.len == b.len){ return a.letter > b.letter; } return a.len < b.len; } bool check(){ for(int i = 1; i <= k; i++){ appeared[i] = false; } lst = '%'; for(int i = 1; i <= n; i++){ if(lett[i] != '*'){ alb = lett[i] - 'a' + 1; if(appeared[alb] && lst != lett[i]){ return false; } lst = lett[i]; appeared[alb] = true; } } return true; } void delet(int num){ exsit[num] = false; for(int i = shorten[num].l; i <= shorten[num].r; i++){ lett[i] = '*'; } return; } int main(){ freopen("seq.in", "r", stdin); freopen("seq.out", "w", stdout); cin >> n >> k >> type; R = 1, L = 1; for(int i = 1; i <= n; i++){ cin >> lett[i]; if(lett[i] == lett[i - 1] || i == 1){ R = i; } else{ cnt++; shorten[cnt].l = L; shorten[cnt].r = R; shorten[cnt].len = (R - L) + 1; shorten[cnt].letter = lett[i - 1]; L = R = i; } if(i == n){ cnt++; shorten[cnt].l = L; shorten[cnt].r = R; shorten[cnt].len = (R - L) + 1; shorten[cnt].letter = lett[i]; } exsit[cnt] = true; } sort(shorten + 1, shorten + cnt + 1, cmp); ans = n; flg = 0; while(!check() && ans > 0 && flg < cnt){ flg++; ans -= shorten[flg].len; delet(flg); } cout << ans << endl; if(type == 0){ return 0; } for(int i = 1; i <= n; i++){ if(lett[i] != '*'){ cout << lett[i]; } } cout << endl; return 0; }