题目内容
原题链接
给定两个长度均为
n
n
n 的
01
01
01 字符串
s
1
s1
s1 和
s
2
s2
s2，以及一个正整数
x
x
x ，每次操作有两种选择：
- 选择两个下标
i
i
i 和j
j
j ，同时反转s
1
[
i
]
s1[i]
s1[i] 和s
1
[
j
]
s1[j]
s1[j] ，代价为x
x
x - 选择一个下标
i
i
i 满足i
+
1
i+1n
，同时反转s
1
[
i
]
服务器托管网
s1[i]
s1[i] 和s
1
[
i
+
1
]
s1[i+1]
s1[i+1] ，代价为1
1
1
问使得
s
1
s1
s1 变为
s
2
s2
s2 的最小代价，如果不能使得
s
1
s1
s1 变为
s
2
s2
s2 ，返回
−
1
-1
−1
数据范围
-
1
≤
n
,
x
≤
500
1leq n,xleq 500
1≤n,x≤500 -
s
1
s1
s1 和s
2
s2
s2 均只包含字符'0'和'1'
题解
这里
s
1
s1
s1 和
s
2
s2
s2 中不同的数位的数量必须为偶数，否则
s
1
s1
s1 必然无法变为
s
2
s2
s2
考虑
f
[
i
]
[
0
/
1
]
f[i][0/1]
f[i][0/1] 表示将
s
1
s1
s1 的前
i
i
i 个字符反转使得
s
1
[
0
:
i
]
=
s
2
[
0
:
i
]
s1[0:i]=s2[0:i]
s1[0:i]=s2[0:i] 的最小代价。
其中
f
[
i
]
[
1
]
f[i][1]
f[i][1] 表示选择了若干次操作
1
1
1 ，最后一次操作
1
1
1 只对下标
i
i
i 使用了，但是未对下标
j
j
j 使用，就是说我有且仅有存在一次操作
1
1
1 满足只选择了下标
i
i
i ，还未确定下标
j
j
j 。
状态转移：
// 第 i 位选择操作 2
f[i][0] = min(f[i][0], f[i - 2][0] + p[i - 1] - p[i - 2]);
f[i][1] = min(f[i][1], f[i - 2][1] + p[i - 1] - p[i - 2]);
// 第 i 位选择操作 1
f[i][0] = min(f[i][0], f[i - 1][1]);
f[i][1] = min(f[i][1], f[i - 1][0] + x);
时间复杂度：
O
服务器托管网 (
n
)
O(n)
O(n)
代码
class Solution {
public:
int minOperations(string s1, string s2, int x) {
vectorint> p;
for (int i = 0; i s1.size(); ++i)
if (s1[i] != s2[i]) p.push_back(i);
int m = p.size();
if (m % 2 == 1) return -1;
if (m == 0) return 0;
vectorvectorint>> f(m + 1, vectorint>(2, 0x3f3f3f3f));
f[0][0] = 0;
f[1][1] = x;
for (int i = 2; i m; ++i) {
// 第 i 位选择操作 2
f[i][0] = min(f[i][0], f[i - 2][0] + p[i - 1] - p[i - 2]);
f[i][1] = min(f[i][1], f[i - 2][1] + p[i - 1] - p[i - 2]);
// 第 i 位选择操作 1
f[i][0] = min(f[i][0], f[i - 1][1]);
f[i][1] = min(f[i][1], f[i - 1][0] + x);
}
return f[m][0];
}
};
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
