求调,悬2关
查看原帖
求调,悬2关
373198
WhileTrueRP楼主2023/11/14 17:40
#include<bits/stdc++.h>
using namespace std;
const int N = 80;
int dp[N][N][N][3];
int vv[N],kk[N],aa[N];
int cnt_v,cnt_k,cnt_a;
string s;
int main(){
	int n;
	scanf("%d",&n);
	cin>>s;
	for(int i=0;i<s.length();i++){
		if(s[i] == 'V'){
			vv[++cnt_v] = i+1;
		}else if(s[i] == 'K'){
			kk[++cnt_k] = i+1;
		}else{
			aa[++cnt_a] = i+1;
		}
	}
	// 0 为最后一个不是 V 
	memset(dp,0x3f,sizeof dp);
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	for(int i=0;i<=cnt_v;i++){
		for(int j=0;j<=cnt_k;j++){
			for(int k=0;k<=cnt_a;k++){
				if(i){
					dp[i][j][k][0] = min(dp[i-1][j][k][0] + (vv[i]-(i+j+k)),dp[i-1][j][k][1] + (vv[i]-(i+j+k)));
					dp[i][j][k][0] = min(dp[i-1][j][k][2] + (vv[i]-(i+j+k)),dp[i][j][k][0]);
				}
				if(j){
					dp[i][j][k][1] = min(dp[i][j-1][k][1] + (kk[j]-(i+j+k)),dp[i][j-1][k][2] + (kk[j]-(i+j+k)));
				}
				if(k){
					dp[i][j][k][2] = min(dp[i][j][k-1][0] + (aa[k]-(i+j+k)),dp[i][j][k-1][1] + (aa[k]-(i+j+k)));
					dp[i][j][k][2] = min(dp[i][j][k-1][2] + (aa[k]-(i+j+k)),dp[i][j][k][2]);
				}
				puts("!");
			}
		}
	}
	printf("%d",min(dp[cnt_v][cnt_k][cnt_a][0],min(dp[cnt_v][cnt_k][cnt_a][1],dp[cnt_v][cnt_k][cnt_a][2])));
}
2023/11/14 17:40
加载中...