1、\(CF771D\ Bear\ and\ Company\)（原题，比赛时改为多组数据）
一道毒瘤\(dp\)题，\(dp[i][j][k][0/1]\)表示有\(i\)个\(V\),有\(j\)个\(K\),有\(k\)个\(X\)所用的最小移动数
那么可以得出状态转移方程：
\[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]])));\]
#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]));}
}
