20240117

标签：return int rep 20240117 define dp size

从whk如活着回来了~~~

觉得还是日更好 以后就每天写一点喵 主要是文章太少看着难受

CF771D Bear and Company

肯定是 \(dp\)， 然后自己想的就没了qwq

考虑如下的状态 \(dp_{v,k,x,0/1}\) 表示当前用了 \(v,k,x\) 个每种字符，最后一个字符是不是 v 的最小操作数

考虑转移，每次多一个字符一定选择最近的这个字符，会产生的新的交换次数可以 \(\mathcal{O}(N)\) 算，总时间复杂度是 \(\mathcal{O}(N^4)\) 的

看巨佬题解好像可以把这个计算做到 \(log\) 和 \(O(1)\)

// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 75 + 10;

// bool st;
int n;
int dp[N][N][N][2];
char s[N];
vector<int> v, k, x;
// bool en;

int calc(int a, int b, int c, int p)
{
    int cnt = 0;
    if (!v.empty())
        rep(i, a, v.size() - 1)
        {
            if (v[i] >= p)
                break;
            cnt++;
        }
    if (!k.empty())
        rep(i, b, k.size() - 1)
        {
            if (k[i] >= p)
                break;
            cnt++;
        }
    // cerr << "flag" << endl;
    if (!x.empty())
        rep(i, c, x.size() - 1)
        {
            if (x[i] >= p)
                break;
            cnt++;
        }
    return cnt;
}

void solve()
{
    cin >> n;
    cin >> (s + 1);
    rep(i, 1, n)
    {
        if (s[i] == 'V')
            v.push_back(i);
        else if (s[i] == 'K')
            k.push_back(i);
        else
            x.push_back(i);
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0] = 0;
    rep(a, 0, v.size())
    {
        rep(b, 0, k.size())
        {
            rep(c, 0, x.size())
            {
                rep(i, 0, 1)
                {
                    if (a < v.size())
                        dp[a + 1][b][c][1] = min(dp[a + 1][b][c][1], dp[a][b][c][i] + calc(a, b, c, v[a]));
                    if (b < k.size() && !i)
                        dp[a][b + 1][c][0] = min(dp[a][b + 1][c][0], dp[a][b][c][i] + calc(a, b, c, k[b]));
                    if (c < x.size())
                        dp[a][b][c + 1][0] = min(dp[a][b][c + 1][0], dp[a][b][c][i] + calc(a, b, c, x[c]));
                }
            }
        }
    }
    cout << min(dp[v.size()][k.size()][x.size()][0], dp[v.size()][k.size()][x.size()][1]) << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}

标签：return,int,rep,20240117,define,dp,size
From： https://www.cnblogs.com/xiaruize/p/17971254