[HOJ] 62 - Words

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 1005
int dp[2][N][27];
char in[N];
struct P{ int x,y; };
vector<P> s;
int main(){
    int n,k,ans=N,add,i,a,b,c,L,R,p,o;
    scanf("%d%d%s",&n,&k,in);
    for(i=0;i<n;i++){
        if(!i || in[i]!=in[i-1]) add=0;
        add++;
        if(i==n-1 || in[i]!=in[i+1]){
            s.push_back((P){add,in[i]-'A'+1});
        }
    }
    memset(dp[1],-1,sizeof(dp[1]));
    dp[1][k][0]=0;
    add=0;
    p=0;
    for(i=0;i<s.size();i++){
        memset(dp[0],-1,sizeof(dp[0]));
        add+=s[i].y;
        o=p;
        p=N;
        for(a=max(k-add,0);a<=k;a++)
        for(b=0;b<=26;b++)
        if(dp[1][a][b]!=-1 && dp[1][a][b]<=min(unsigned(n-k),o+s.size()-i)){
            for(c=1;c<=26;c++){
                L=1-(b==c);
                R=s[i].x;
                if(s[i].y==c){
                    if(dp[0][a][c]==-1 || dp[1][a][b]+L<dp[0][a][c])
                        dp[0][a][c]=dp[1][a][b]+L;
                    p=min(p,dp[0][a][c]);
                }
                else if(a-R>=0){
                    if(dp[0][a-R][c]==-1 || dp[1][a][b]+L<dp[0][a-R][c])
                        dp[0][a-R][c]=dp[1][a][b]+L;
                    p=min(p,dp[0][a-R][c]);
                }
            }
        }
        memcpy(dp[1],dp[0],sizeof(dp[1]));
    }
    for(a=0;a<=k;a++)
    for(b=0;b<=26;b++)
    if(dp[1][a][b]!=-1)
        ans=min(ans,dp[1][a][b]);
    printf("%d\n",ans);
}