有n个城市，城市从0到n-1进行编号。小美最初住在k号城市中
在接下来的m天里，小美每天会收到一个任务
她可以选择完成当天的任务或者放弃该任务
第i天的任务需要在ci号城市完成，如果她选择完成这个任务
若任务开始前她恰好在ci号城市，则会获得ai的收益
若她不在ci号城市，她会前往ci号城市，获得bi的收益
当天的任务她都会当天完成
任务完成后，她会留在该任务所在的ci号城市直到接受下一个任务
如果她选择放弃任务，她会停留原地，且不会获得收益
小美想知道，如果她合理地完成任务，最大能获得多少收益
输入描述: 第一行三个正整数n, m和k，表示城市数量，总天数，初始所在城市
第二行为m个整数c1, c2,… cm，其中ci表示第i天的任务所在地点为ci
第三行为m个整数a1, a2,… am，其中ai表示完成第i天任务且地点不变的收益
第四行为m个整数b1, b2,… bm，其中bi表示完成第i天的任务且地点改变的收益
0 <= k, ci <= n <= 30000
1 <= m <= 30000
0 <= ai, bi <= 10^9
输出描述 输出一个整数，表示小美合理完成任务能得到的最大收益。
1.递归。
时间复杂度：O(N2)。
空间复杂度：O(N2)。
2.线段树。
时间复杂度：O(N*logN)。
空间复杂度：O(N**2)。
代码用rust编写。代码如下：
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.push(rand::thread_rng().gen_range(0, v));
}
ans
}执行结果如下：
