【CodeForces】790 C. Bear and Company 动态规划

【题目】C. Bear and Company

【题意】给定大写字母字符串，交换相邻字符代价为1，求最小代价使得字符串不含"VK"子串。n<=75。

【算法】动态规划

【题解】关键在于表示状态，我们将确定下来的前若干个固定作为状态，后面新加的字符不会进入固定的前若干个。（为了方便，非'V''K'的字符皆为‘X'）

由于相同字符显然不可能跨越，那么前若干个的有效信息只有：它是由前v个’V'，前k个‘K'，前x个’X'组成的，最后一个字符是否’V'，即f[v][k][x][0/1]。

转移时枚举新加入的字符，问题在于统计新加入字符前有多少未固定字符，就是加入这个字符的代价。

假设0是'V'，1是‘K'，2是’X'，很容易预处理p[i][0]表示第i个'V'的位置，c[i][0]表示前i个位置‘V'的数量（1和2同理），然后就很容易计算了。

如果推不清楚可以参考代码，很好理解。

复杂度O(n^3)。

#include<cstdio>

#include<cstring>

int n,p[][],c[][],f[][][][],V,K,X;

char s[];

int min(int a,int b){return a<b?a:b;}

int r(int o,int v,int k,int x){return o-min(c[o][],v)-min(c[o][],k)-min(c[o][],x);}

int main(){

    scanf("%d%s",&n,s+);

    for(int i=;i<=n;i++){

        for(int j=;j<;j++)c[i][j]=c[i-][j];

        if(s[i]=='V')V++,p[V][]=i,c[i][]++;else

        if(s[i]=='K')K++,p[K][]=i,c[i][]++;else

        X++,p[X][]=i,c[i][]++;

    }

    memset(f,0x3f,sizeof(f));

    f[][][][]=;

    for(int i=;i<=V;i++)

        for(int j=;j<=K;j++)

            for(int k=;k<=X;k++){

                int Q=min(f[i][j][k][],f[i][j][k][]);

                f[i+][j][k][]=min(f[i+][j][k][],Q+r(p[i+][],i+,j,k));

                f[i][j+][k][]=min(f[i][j+][k][],f[i][j][k][]+r(p[j+][],i,j+,k));

                f[i][j][k+][]=min(f[i][j][k+][],Q+r(p[k+][],i,j,k+));

            }

    printf("%d",min(f[V][K][X][],f[V][K][X][]));

    return ;

}