codeforces 724D

注意到要字典序最小，从而变为水题。

从a选到z，每次必然是先看选部分当前字符x是否能满足覆盖，若不能则选上所有的字母x，不然break，输出答案。

进行26次dp即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 
12 #define N 100010
13 #define INF 0x3f3f3f3f
14 
15 using namespace std;
16 
17 struct node{
18     int x,v;
19     bool operator<(const node &a)const{
20         return v>a.v;
21     }
22 };
23 
24 char S[N];
25 char ansv[N];
26 int n,m,tot,f[N];
27 priority_queue<node> q;
28 
29 int main(){
30 //    freopen("D.txt","r",stdin);
31     scanf("%d%s",&m,S);
32     n=strlen(S);
33     
34     for(char x='a';x<='z';x++){
35         for(int i=1;i<=n;i++) f[i]=INF;
36         f[0]=0;
37         
38         while(!q.empty()) q.pop();
39         q.push((node){0,0});
40         int cnt=0;
41         
42         for(int i=1;i<=n;i++){
43             if(S[i-1]>x) continue;
44             if(S[i-1]==x) cnt++;
45             
46             while(!q.empty()){
47                 node tmp=q.top();
48         
49                 if(tmp.x<i-m) q.pop();
50                 else{
51                     if(S[i-1] == x) f[i] = tmp.v + 1;
52                     else f[i] = tmp.v;
53                     break;
54                 }
55             }
56             
57             if(f[i]<INF) q.push((node){i,f[i]});
58         }
59         
60         int ans=INF;
61         for(int i=n-m+1;i<=n;i++) ans = min(ans,f[i]);
62         
63         if(ans<INF){
64             while(ans--) ansv[++tot]=x;
65             break;
66         }
67         else while(cnt--) ansv[++tot]=x;
68     }
69     
70     for(int i=1;i<=tot;i++) putchar(ansv[i]);
71     putchar('
');
72     return 0;
73 }
74 
75

View Code