# 2022-12-12：有n个城市，城市从0到n-1进行编号。小美最初住在k号城市中 在接下来的m天里

2022-12-12：有n个城市，城市从0到n-1进行编号。小美最初住在k号城市中

0 <= k, ci <= n <= 30000
1 <= m <= 30000
0 <= ai, bi <= 10^9

1.递归。

2)。

2.线段树。

2)。

``````use rand::Rng;
use std::iter::repeat;
fn main() {
let nn: i32 = 100;
let mm: i32 = 100;
let vv: i32 = 10000;
let test_time: i32 = 5000;
println!("测试开始");
for i in 0..test_time {
let n: i32 = rand::thread_rng().gen_range(0, nn) + 1;
let m: i32 = rand::thread_rng().gen_range(0, mm) + 1;
let k: i32 = rand::thread_rng().gen_range(0, n);
let mut c = random_array(m, n);
let mut a = random_array(m, vv);
let mut b = random_array(m, vv);
let ans1 = max_porfit1(n, m, k, &mut c, &mut a, &mut b);
let ans2 = max_porfit2(n, m, k, &mut c, &mut a, &mut b);
if ans1 != ans2 {
println!("出错了!");
println!("i = {}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}

// 暴力方法
// 时间复杂度O(N^2)
// 为了验证
fn max_porfit1(
n: i32,
m: i32,
k: i32,
c: &mut Vec<i32>,
a: &mut Vec<i32>,
b: &mut Vec<i32>,
) -> i32 {
let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take(m as usize).collect())
.take(n as usize)
.collect();
return process1(k, 0, m, c, a, b, &mut dp);
}

// cur : 小美当前在哪！
// i : 当前面临的是任务编号！
// m : 一共有多少任务，固定
// c[i] : 第i号任务要在哪个城里完成
// a[i] : 恰好在！收益
// b[i] : 赶过去！收益
// 返回 : i....... 小美获得的最大收益
fn process1(
cur: i32,
i: i32,
m: i32,
c: &mut Vec<i32>,
a: &mut Vec<i32>,
b: &mut Vec<i32>,
dp: &mut Vec<Vec<i32>>,
) -> i32 {
if i == m {
return 0;
}
if dp[cur as usize][i as usize] != -1 {
return dp[cur as usize][i as usize];
}
// 可能性1 : 不做任务，彻底放弃，留在原地
let p1 = process1(cur, i + 1, m, c, a, b, dp);
// 可能性2 : 做任务，要看看cur在哪，来获得收益
let mut p2 = 0;
if cur == c[i as usize] {
p2 = a[i as usize] + process1(c[i as usize], i + 1, m, c, a, b, dp);
} else {
p2 = b[i as usize] + process1(c[i as usize], i + 1, m, c, a, b, dp);
}
let ans = get_max(p1, p2);
dp[cur as usize][i as usize] = ans;
return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}

// 正式方法
// 时间复杂度O(N*logN)
fn max_porfit2(
n: i32,
m: i32,
k: i32,
c: &mut Vec<i32>,
a: &mut Vec<i32>,
b: &mut Vec<i32>,
) -> i32 {
let mut st = SegmentTree::new(n);
st.update(k, 0);
let mut ans = 0;
for i in 0..m {
// c[i]
let cur_ans = get_max(
get_max(
st.max(0, c[i as usize] - 1),
st.max(c[i as usize] + 1, n - 1),
) + b[i as usize],
st.max(c[i as usize], c[i as usize]) + a[i as usize],
);
ans = get_max(ans, cur_ans);
st.update(c[i as usize], cur_ans);
}
return ans;
}

struct SegmentTree {
n: i32,
max: Vec<i32>,
}
impl SegmentTree {
fn new(nn: i32) -> Self {
let n = nn;
let max: Vec<i32> = repeat(i32::MIN).take(((n + 1) << 2) as usize).collect();
Self { n, max }
}

fn max(&mut self, mut l: i32, mut r: i32) -> i32 {
l += 1;
r += 1;
if l > r {
return i32::MIN;
}
return self.max0(l, r, 1, self.n, 1);
}

fn update(&mut self, mut i: i32, v: i32) {
i += 1;
self.update0(i, i, v, 1, self.n, 1);
}

fn push_up(&mut self, rt: i32) {
self.max[rt as usize] = get_max(
self.max[(rt << 1) as usize],
self.max[(rt << 1 | 1) as usize],
);
}

fn update0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {
if ll <= l && r <= rr {
self.max[rt as usize] = get_max(self.max[rt as usize], cc);
return;
}
let mid = (l + r) >> 1;
if ll <= mid {
self.update0(ll, rr, cc, l, mid, rt << 1);
}
if rr > mid {
self.update0(ll, rr, cc, mid + 1, r, rt << 1 | 1);
}
self.push_up(rt);
}

fn max0(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {
if ll <= l && r <= rr {
return self.max[rt as usize];
}
let mid = (l + r) >> 1;
let mut left = i32::MIN;
let mut right = i32::MIN;
if ll <= mid {
left = self.max0(ll, rr, l, mid, rt << 1);
}
if rr > mid {
right = self.max0(ll, rr, mid + 1, r, rt << 1 | 1);
}
return get_max(left, right);
}
}

// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut ans = vec![];
for i in 0..n {
}
ans
}
``````

(=￣ω￣=)··· 暂无内容！

209

10

19

5