D. Bear and Company (cf771D)

D. Bear and Company (cf771D)

tag：dp

题目链接

题意：

给你一串长度为n的字符串，(2<=n<=75),字母全为大写字母，你可以通过一次操作交换任意一对相邻字母。
字符串合法当且仅当不存在”VK“的字串，问你最少通过几次操作使得字符串合法。

做法：

首先观察到n很小，多开几维是必须的
我们设 dp[i][j][k][0/1],表示当前串有i个V,j个K,k个其他字母组成，最后一个字母是否为V
另外，若相邻两字符相同，则交换后的串还是一样，交换没有意义，所以对于相同的字母来说，他们的相对位置不变
下面考虑状态转移
假设我们此时要在串的末尾插入一个字符，我们要让它从原位置到目前的最后，就相当于做一次冒泡，那么我们拿他的原始位置和其他两种已经插入的字符原始位置比较，逆序对个数就是代价

代码：

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N= 80;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
vector<int> a,b,c;
int dp[N][N][N][2]; 

int main(){
    int n; cin>>n;
    string s; cin>>s;
    s = " "+s; 
    for(int i=1;i<=n;i++){
        if(s[i]=='V') a.push_back(i); 
        else if(s[i]=='K') b.push_back(i); 
        else c.push_back(i);
    }
    int sa = a.size(),sb = b.size(),sc = c.size();

    for(int i=0;i<=sa;i++){
        for(int j=0;j<=sb;j++){
            for(int k=0;k<=sc;k++){
                if(i+j+k==0) continue;
                dp[i][j][k][0] = dp[i][j][k][1] = INF;
                if(i){
                    dp[i][j][k][1] = min(dp[i-1][j][k][0],dp[i-1][j][k][1]);
                    for(int t=0;t<j;t++) if(b[t]>a[i-1]) dp[i][j][k][1]++;
                    for(int t=0;t<k;t++) if(c[t]>a[i-1]) dp[i][j][k][1]++;
                }
                if(j){
                    int cnt=dp[i][j-1][k][0]; //如果上一串结尾是V，显然不能放K
                    for(int t=0;t<i;t++) if(a[t]>b[j-1]) cnt++;
                    for(int t=0;t<k;t++) if(c[t]>b[j-1]) cnt++;
                    dp[i][j][k][0]=min(dp[i][j][k][0],cnt);
                }
                if(k){
                    int cnt=min(dp[i][j][k-1][0],dp[i][j][k-1][1]);
                    for(int t=0;t<i;t++) if(a[t]>c[k-1]) cnt++;
                    for(int t=0;t<j;t++) if(b[t]>c[k-1]) cnt++;
                    dp[i][j][k][0]=min(dp[i][j][k][0],cnt);
                }
            }
        }
    }
    cout<<min(dp[sa][sb][sc][0],dp[sa][sb][sc][1])<<le;
    return 0;
}