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

moonfdd 的个人博客 / 20 / 0 / 创建于 1年前

2022-12-12：有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
输出描述输出一个整数，表示小美合理完成任务能得到的最大收益。
来自美团。

答案2022-12-12：

1.递归。
时间复杂度：O(N2)。
空间复杂度：O(N2)。

2.线段树。
时间复杂度：O(NlogN)。
空间复杂度：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
}