Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int MAXN=1e3+5;
- const int MAXM=1e5+5;
- const int mod=1e9+7;
- int n,m,cnt[MAXN][30],f[MAXN][30],g[MAXN][30];
- char x[MAXN];
- int main(){
- int aa; scanf("%d",&aa);
- while(aa--){
- scanf("%d",&m);
- scanf(" %s",x+1); n=strlen(x+1);
- memset(cnt,0,sizeof(cnt));
- int num=0;
- for(int j=1;j<=m;j++) cnt[1][x[j]-'a']++;
- for(int j=0;j<26;j++) num+=(cnt[1][j]!=0);
- for(int j=0;j<26;j++) if (cnt[1][j]!=0) f[1][j]=g[1][j]=num;
- for(int i=m+1;i<=n;i+=m){
- int tag=(i+m-1)/m; num=0;
- for(int j=1;j<=m;j++) cnt[tag][x[i+j-1]-'a']++;
- for(int j=0;j<26;j++) num+=(cnt[tag][j]!=0);
- for(int j=0;j<26;j++) f[tag][j]=g[tag][j]=10000000;
- for(int j=0;j<26;j++){
- if (cnt[tag][j]==0) continue;
- for(int k=0;k<26;k++){
- if (cnt[tag-1][k]==0) continue;
- f[tag][j]=min(f[tag][j],g[tag-1][k]+num-(j==k));
- }
- for(int k=0;k<26;k++){
- if (cnt[tag][k]==0) continue;
- if ((k!=j) || (k==j && cnt[tag][k]==m)) g[tag][k]=min(g[tag][k],f[tag][j]);
- }
- }
- }
- int ans=10000000;
- for(int i=0;i<26;i++)
- if (cnt[n/m][i]!=0) ans=min(ans,f[n/m][i]);
- printf("%d\n",ans);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment