小红拿到了一个仅由r、e、d组成的字符串
她定义一个字符e为"好e" : 当且仅当这个e字符和r、d相邻
例如"reeder"只有一个"好e",前两个e都不是"好e",只有第三个e是"好e"
小红每次可以将任意字符修改为任意字符,即三种字符可以相互修改
她希望"好e"的数量尽可能多
小红想知道,自己最少要修改多少次
输入一个只有r、e、d三种字符的字符串
长度 <= 2 * 10^5。
输出最小修改次数。
动态规划。
奇数,1,3,5,7一定是e。
代码用rust编写。代码如下:
use std::iter::repeat;
fn main() {
let str = "rrredrr";
let ans = min_cost(str); //dereder
println!("ans = {}", ans);
}
fn min_cost(str: &str) -> i32 {
let n = str.len() as i32;
if n < 3 {
return -1;
}
let mut arr: Vec<i32> = repeat(0).take(n as usize).collect();
// d认为是0,e认为是1,r认为是2
let strc: Vec<char> = str.chars().collect();
for i in 0..n {
let cur = strc[i as usize];
if cur == 'd' {
arr[i as usize] = 0;
} else if cur == 'e' {
arr[i as usize] = 1;
} else {
arr[i as usize] = 2;
}
}
// 通过上面的转化,问题变成了:
// 1的左右,一定要被0和2包围,这个1才是"好1"
// 请让"好1"的尽量多,返回最少的修改代价
let mut max_good = 0;
let mut min_cost = i32::MAX;
for prepre in 0..3 {
for pre in 0..3 {
let mut cost = if arr[0] == prepre { 0 } else { 1 };
cost += if arr[1] == pre { 0 } else { 1 };
let cur = process(&mut arr, 2, prepre, pre);
if cur.max_good > max_good {
max_good = cur.max_good;
min_cost = cur.min_cost + cost;
} else if cur.max_good == max_good {
min_cost = get_min(min_cost, cur.min_cost + cost);
}
}
}
return min_cost;
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
struct Info {
max_good: i32,
min_cost: i32,
}
impl Info {
fn new(a: i32, b: i32) -> Self {
Self {
max_good: a,
min_cost: b,
}
}
}
// 暴力递归
// 可以自己改成动态规划
// arr[index-2]位置的数值是prepre
// arr[index-1]位置的数值是pre
// 在这种情况下,请让arr[index...]上的好1尽量多
// 返回:
// 尽量多的"好1",是多少?
// 得到尽量多的"好1",最小代价是多少?
fn process(arr: &mut Vec<i32>, index: i32, prepre: i32, pre: i32) -> Info {
if index == arr.len() as i32 {
return Info::new(0, 0);
}
// 可能性1,arr[index],变成0
let mut p1_value = if prepre == 2 && pre == 1 { 1 } else { 0 };
let mut p1_cost = if arr[index as usize] == 0 { 0 } else { 1 };
let mut info = process(arr, index + 1, pre, 0);
p1_value += info.max_good;
p1_cost += info.min_cost;
// 可能性2,arr[index],变成1
let mut p2_value = 0;
let mut p2_cost = if arr[index as usize] == 1 { 0 } else { 1 };
info = process(arr, index + 1, pre, 1);
p2_value += info.max_good;
p2_cost += info.min_cost;
// 可能性3,arr[index],变成2
let mut p3_value = if prepre == 0 && pre == 1 { 1 } else { 0 };
let mut p3_cost = if arr[index as usize] == 2 { 0 } else { 1 };
info = process(arr, index + 1, pre, 2);
p3_value += info.max_good;
p3_cost += info.min_cost;
// 开始决策,选出三种可能性中的最优解
let mut max_good = 0;
let mut min_cost = i32::MAX;
if p1_value > max_good {
max_good = p1_value;
min_cost = p1_cost;
} else if p1_value == max_good {
min_cost = get_min(min_cost, p1_cost);
}
if p2_value > max_good {
max_good = p2_value;
min_cost = p2_cost;
} else if p2_value == max_good {
min_cost = get_min(min_cost, p2_cost);
}
if p3_value > max_good {
max_good = p3_value;
min_cost = p3_cost;
} else if p3_value == max_good {
min_cost = get_min(min_cost, p3_cost);
}
return Info::new(max_good, min_cost);
}
执行结果如下: