D2. Zero-One (Hard Version)
我们由D1可知当我们的y小于x/2时 我们可以用2y来减小相邻的cost
那我们考虑要是y比较大的时候 我们也可以用多个x来减小cost
我们可以轻松的写出get函数
int get(int l,int r) {
if (l + 1 == r)return min(2 * y, x);
else return min(x * (r - l), y);
}
最后我们考虑dp[l][r] 表示为区间[l,r]需要的min_cost
状态转移:
我们每次区间长度+2
我们可以对她前面两个做一次x操作 或者对他后面两个做一次x操作(这样就可以保证dp的完备性
或者是对他两个端点做一次y操作(因为只有这样才是最优的情况
注意这里可能两个端点在a数组里都是0 但是没关系 我们主要的只是要其“路径”的长度(类似于这道题[https://codeforces.com/problemset/problem/1680/E])
dp[i][j] =
min({dp[i + 1][j - 1] + get(pos[i], pos[j]),
dp[i + 2][j] + get(pos[i], pos[i + 1]),
dp[i][j - 2] + get(pos[j - 1], pos[j])});
最后我们加上第一题的特判即可
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,x,y,dp[5050][5050];
int get(int l,int r) {
if (l + 1 == r)return min(2 * y, x);
else return min(x * (r - l), y);
}
void solve() {
cin >> n >> x >> y;
vector<char> a(n + 1), b(n + 1);
vector<int> pos;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)cin >> b[i];
for (int i = 1; i <= n; i++) {
if (a[i] != b[i])pos.push_back(i);
}
if (pos.size() % 2 == 1) {
cout << "-1" << endl;
return;
}
if (pos.size() == 0) {
cout << "0" << endl;
return;
}
if (pos.size() == 2) {
if (pos[0] + 1 == pos[1])cout << min(2 * y, x) << endl;
else cout << min(y, x * (pos[1] - pos[0])) << endl;
return;
}
if (y <= x) {
cout << pos.size() / 2 * y << endl;
return;
}
for (int len = 2; len <= pos.size(); len += 2) {
for (int i = 0, j = len + i - 1; j < pos.size(); j++, i++) {
if (len == 2)dp[i][j] = get(pos[i], pos[j]);
else dp[i][j] = min({dp[i + 1][j - 1] + get(pos[i], pos[j]), dp[i + 2][j] + get(pos[i], pos[i + 1]),
dp[i][j - 2] + get(pos[j - 1], pos[j])});
}
}
cout << dp[0][pos.size() - 1] << endl;
}
signed main(){
fast
int T;cin>>T;
while(T--) {
solve();
}
return ~~(0^_^0);
}
标签:get,int,D2,min,Codeforces,pos,821,dp,define
From: https://www.cnblogs.com/ycllz/p/16711954.html