1、\(CF771D\ Bear\ and\ Company\)（原题，比赛时改为多组数据）

一道毒瘤\(dp\)题，\(dp[i][j][k][0/1]\)表示有\(i\)个\(V\),有\(j\)个\(K\),有\(k\)个\(X\)所用的最小移动数

那么可以得出状态转移方程：

#include<bits/stdc++.h>

using namespace std;

int sumv[1000000],sumk[1000000],T,sumx[1000000],dp[200][200][200][2],V[10000],K[10000],X[10000];

char y[100000],x[100000];

int main(){

    scanf("%d",&T);

    while (T--){

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

        dp[0][0][0][0]=0;

        dp[0][0][0][1]=0;

        scanf("\n%s",x);

        int N=strlen(x);

        for (int i=0;i<N;i++){

            sumv[i]=sumv[i-1];

            sumk[i]=sumk[i-1];

            sumx[i]=sumx[i-1];

            if (x[i]=='V'){

                sumv[i]=sumv[i-1]+1;

                V[sumv[i]]=i;

            }else if (x[i]=='K'){

                sumk[i]=sumk[i-1]+1;

                K[sumk[i]]=i;

            }else{

                sumx[i]=sumx[i-1]+1;

                X[sumx[i]]=i;

            }

        }

        for (int i=0;i<=sumv[N-1];i++){

            for (int j=0;j<=sumk[N-1];j++){

                for (int k=0;k<=sumx[N-1];k++){

                    if (i+j+k==0){

                        continue;

                    }

                    if (i) dp[i][j][k][1]=min(dp[i][j][k][1],min(dp[i-1][j][k][0],dp[i-1][j][k][1])+V[i]-(i-1+min(j,sumk[V[i]])+min(k,sumx[V[i]])));

                    if (j) dp[i][j][k][0]=min(dp[i][j][k][0],dp[i][j-1][k][0]+K[j]-(j-1+min(i,sumv[K[j]])+min(k,sumx[K[j]])));

                    if (k) dp[i][j][k][0]=min(dp[i][j][k][0],min(dp[i][j][k-1][0],dp[i][j][k-1][1])+X[k]-(k-1+min(j,sumk[X[k]])+min(i,sumv[X[k]])));

                }

            }

        }

        printf("%d\n",min(dp[sumv[N-1]][sumk[N-1]][sumx[N-1]][0],dp[sumv[N-1]][sumk[N-1]][sumx[N-1]][1]));

    }

}