2022-12-08：给定n棵树，和两个长度为n的数组a和b
i号棵树的初始重量为ai，i号树每天的增长重量为bi
你每天最多能砍1棵树，这天收益 = 砍的树初始重量 砍的树增长到这天的总增重
给定m，表示你有m天，返回m天内你获得的最大收益。
答案2022-12-08：
排序 贪心。
代码用rust编写。代码如下：
代码语言：rust复制use std::iter::repeat;
fn main() {
unsafe {
let ins = [2, 2, 1, 10, 10, 1, 1, 2, 2, 8, 10, 2, 3];
let mut ii = 0;
let testCases = ins[ii];
ii = 1;
for i in 0..testCases {
//
let n = ins[ii];
ii = 1;
let m = ins[ii];
ii = 1;
for j in 0..n {
tree[j as usize][0] = ins[ii];
ii = 1;
}
for j in 0..n {
tree[j as usize][1] = ins[ii];
ii = 1;
}
let ans = max_weight(n, m);
println!("ans = {}", ans);
}
}
}
static mut tree: [[i32; 2]; 250] = [[0; 2]; 250];
static mut dp: [[i32; 250]; 250] = [[0; 250]; 250];
// tree[][]
// i棵树，初始重量 ， tree[i][0]
// i棵树，每天的增长重量 ，tree[i][1]
fn max_weight(n: i32, m: i32) -> i32 {
unsafe {
//Arrays.sort(tree, 0, n, (o1, o2) -> o1[1] - o2[1]);
tree[..n as usize].sort_by(|a, b| a[1].cmp(&b[1]));
dp[0][0] = tree[0][0];
for i in 1..n {
dp[i as usize][0] = get_max(dp[(i - 1) as usize][0], tree[i as usize][0]);
}
for j in 1..m {
dp[0][j as usize] = dp[0][(j - 1) as usize] tree[0][1];
}
for i in 1..n {
for j in 1..m {
dp[i as usize][j as usize] = get_max(
dp[(i - 1) as usize][j as usize],
dp[(i - 1) as usize][(j - 1) as usize]
tree[i as usize][0]
tree[i as usize][1] * j,
);
}
}
return dp[(n - 1) as usize][(m - 1) as usize];
}
}
fn get_max<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}执行结果如下：
在这里插入图片描述左神java代码
