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("
%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
",min(dp[sumv[N-1]][sumk[N-1]][sumx[N-1]][0],dp[sumv[N-1]][sumk[N-1]][sumx[N-1]][1]));
}
}