Zero-One (Hard Version)

Created by LXC on Sun Nov 5 02:49:44 2023

https://codeforces.com/problemset/problem/1733/D2

ranting: 2000

tag: dp, greedy

problem

给出两个长度都为n的01字符串a和b。

现在每次操作可以选择a中两个索引l和r，$(l<r)$。

让$a_l$变为$1-a_l$，让$a_r$变为$1-a_r$

如果$l+1=r$，则操作代价为x否则操作代价为y。

问让a变为b的最小代价。

$5 \le n \le 5000$

$1 \le x, y\le 10^9$

solution

我们只要考虑$a_i \ne b_i$的所有索引i。我们预处理出这些索引到一个数组v。

如果数组v的大小为sz，sz=0则说明a和b已经相等，无需操作，输出0。

如果sz为奇数，则最后会存在一个i不满足$a_i=b_i$，输出-1。

如果$x\ge y$：

• 当sz为2，考虑两个索引是否相邻，不相邻花费y，相邻花费min(2y, x)，（n的大小至少为5，我们可以拆分成两次不相邻操作）。
• 当sz超过2，一定可以拆分为sz/2次不相邻的操作。花费固定为sz/2*y

如果$x < y$，需要考虑区间动态规划。

定义$f_{l,r}$为子数组$v_{l…r}$内部两两匹配所花费的最小代价。

我们定义$cost_{l,r}$为操作$v_l$和$v_r$两个索引的最小代价。

当相邻时，即$v_l + 1 = v_r$，最小代价是x，（y>x情况下，拆分成两次不相邻的操作代价为2y显然大于x）

当不相邻时，即$v_l + 1 \ne v_r$，最小代价是$min((v_r-v_l)x, y)$，（我们可以将不相邻操作看成若干相邻操作的组合）

状态转移只有三种情况，$f_{l,r} = min(cost_{l, l+1}+f_{l+2, r}, cost_{r-1, r}+f_{l, r-2}, cost_{l, r}+f_{l+1, r-1})$

设$l < l’ < l’’$，$v_{l}$和$v_{l’}$操作其代价不会比 $v_{l}$和$v_{l’}$操作 更优

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    ll n, x, y;
    cin >> n >> x >> y;
    string a, b;
    cin >> a >> b;
    vector<int> v;
    for (int i=0; i<n; i++) {
        if (a[i] != b[i]) v.push_back(i);
    }
    int sz = v.size();
    if (sz == 0) {
        cout << "0\n";
        return ;
    }
    if (sz%2) {
        cout << "-1\n";
        return ;
    }
    if (x >= y) {
        if (sz == 2) {
            cout << (v[0]+1 == v[1] ? min(2*y, x) : y) << "\n";
        } else {
            cout << sz/2*y << "\n";
        }
        return ;
    }
    ll INF = 1e18;
    vector<vector<ll>> dp(sz, vector<ll>(sz, INF));
    auto cost = [&](int l, int r)->ll {
        return v[l] + 1 == v[r] ? x : min((v[r]-v[l])*x, y);
    };
    auto dfs = [&](auto self, int l, int r) {
        if (dp[l][r] != INF) return dp[l][r];
        if (l+1 == r) {
            return dp[l][r] = cost(l, r);
        }
        dp[l][r] = min({dp[l][r], 
                          cost(l,l+1)+self(self, l+2, r), 
                          cost(r-1, r)+self(self, l, r-2), 
                          cost(l, r)+self(self, l+1, r-1)});
        return dp[l][r];
    };
    cout << dfs(dfs, 0, sz-1) << "\n"; 
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}