题目描述：
给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 x 。
你可以对字符串 s1 执行以下操作 任意次 ：
- 选择两个下标
i 和 j ，将 s1[i] 和 s1[j] 都反转，操作的代价为 x 。 - 选择满足
i < n - 1 的下标 i ，反转 s1[i] 和 s1[i + 1] ，操作的代价为 1 。
请你返回使字符串 s1 和 s2 相等的 最小 操作代价之和，如果无法让二者相等，返回 -1 。
注意 ，反转字符的意思是将 0 变成 1 ，或者 1 变成 0 。
数据范围：
$1\le n,x\le 500$
$s1,s2$ 只包含 $0,1$
题解：
区间dp：
使用区间 $dp$ ， $dp[i][j]$ 与 $dp[i + 1][j - 1], dp[i + 2][j], dp[i][j-2]$ 有关。
其中合法区间初始化为 $INF$ ，非法区间初始化为 $0$ 。
线性dp：
考虑一个前缀区间，如果区间长度为偶数，则 $dp[i - 1]$ 区间长度为奇数，剩余一个未匹配，需要进行一次操作一。
区间长度为奇数时， $dp[i-1]$ 区间长度是偶数，不存在未匹配的。
也可以用另一种线性递推：
针对 $dp[i],a[i]$ ，第一种操作，花费 $x$ ，那么相当于对 $a[i]$ 花费 $x/2$ 。 $dp[i] = dp[i-1] + x/2$ 。
第二种操作， $dp[i] = dp[i - 2] + a[i] - a[i - 1]$ 。
两者取最小值即可，但是存在 $x/2$ 不好做，可以将所有的数字都乘以 $2$ 。最后的答案除以 $2$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
void dfs(int l, int r)
{
}
int minOperations(string s1, string s2, int x)
{
int n = s1.size();
int sum = 0;
vector<int> a;
vector<bool> vis(n);
for (int i = 0; i < n; ++i)
{
if (s1[i] != s2[i])
{
a.emplace_back(i);
sum++;
}
}
if (sum & 1)
return -1;
if (sum == 0)
return 0;
int m = a.size();
vector<vector<int>> dp(m, vector<int>(m, 0));
for (int i = 0; i < m; ++i)
{
for (int j = i + 1; j < m; ++j)
{
dp[i][j] = INT_MAX;
}
}
for (int len = 2; len <= m; len += 2)
{
for (int i = 0; i + len - 1 <= m - 1; ++i)
{
int j = i + len - 1;
dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + min(x, a[j] - a[i]));
if (i + 2 <= j)
dp[i][j] = min(dp[i][j], dp[i + 2][j] + min(x, a[i + 1] - a[i]));
if (i <= j - 2)
dp[i][j] = min(dp[i][j], dp[i][j - 2] + min(x, a[j] - a[j - 1]));
}
}
return dp[0][m - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minOperations(string s1, string s2, int x)
{
int n = s1.size();
int sum = 0;
vector<int> a;
vector<bool> vis(n);
for (int i = 0; i < n; ++i)
{
if (s1[i] != s2[i])
{
a.emplace_back(i);
sum++;
}
}
if (sum & 1)
return -1;
if (sum == 0)
return 0;
int m = a.size();
vector<int> dp(m, INT_MAX);
dp[0] = 0;
dp[1] = min(x, a[1] - a[0]);
for (int i = 2; i < m; ++i)
{
if (i & 1)
dp[i] = min(dp[i], min(dp[i - 2] + a[i] - a[i - 1], dp[i - 1] + x));
else
dp[i] = min(dp[i], min(dp[i - 2] + a[i] - a[i - 1], dp[i - 1]));
}
return dp[m - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minOperations(string s1, string s2, int x)
{
int n = s1.size();
int sum = 0;
vector<int> a;
vector<bool> vis(n);
for (int i = 0; i < n; ++i)
{
if (s1[i] != s2[i])
{
a.emplace_back(i);
sum++;
}
}
if (sum & 1)
return -1;
if (sum == 0)
return 0;
int m = a.size();
vector<int> dp(m, INT_MAX);
dp[0] = x, dp[1] = min(dp[0] + x, (a[1] - a[0]) * 2);
for (int i = 2; i < m; ++i)
{
dp[i] = min(dp[i - 2] + (a[i] - a[i - 1]) * 2, dp[i - 1] + x);
}
cout << dp[m - 1] << endl;
return dp[m - 1] / 2;
}
};
|