2022-12-22:给定一个数字n,代表数组的长度,给定一个数字m,代表数组每个位置都可以在1~m之间选择数字,所有长度为n的
数组 一个 2022 选择 数字 可以 所有 之间
2023-06-13 09:16:48 时间
2022-12-22:给定一个数字n,代表数组的长度,
给定一个数字m,代表数组每个位置都可以在1~m之间选择数字,
所有长度为n的数组中,最长递增子序列长度为3的数组,叫做达标数组。
返回达标数组的数量。
1 <= n <= 500,
1 <= m <= 10,
500 * 10 * 10 * 10,
结果对998244353取模,
实现的时候没有取模的逻辑,因为非重点。
来自微众银行。
答案2022-12-22:
参考最长递增子序列。
代码用rust编写。代码如下:
use std::iter::repeat;
fn main() {
println!("功能测试开始");
for n in 4..=8 {
for m in 1..=5 {
let ans1 = number1(n, m);
let ans2 = number2(n, m);
if ans1 != ans2 {
println!("{}", ans1);
println!("{}", ans2);
println!("出错了!");
}
}
}
println!("功能测试结束");
}
// 暴力方法
// 为了验证
fn number1(n: i32, m: i32) -> i32 {
let mut a: Vec<i32> = repeat(0).take(n as usize).collect();
return process1(0, n, m, &mut a);
}
fn process1(i: i32, n: i32, m: i32, path: &mut Vec<i32>) -> i32 {
if i == n {
return if length_of_lis(path) == 3 { 1 } else { 0 };
} else {
let mut ans = 0;
for cur in 1..=m {
path[i as usize] = cur;
ans += process1(i + 1, n, m, path);
}
return ans;
}
}
fn length_of_lis(arr: &mut Vec<i32>) -> i32 {
if arr.len() == 0 {
return 0;
}
let mut ends: Vec<i32> = repeat(0).take(arr.len()).collect();
ends[0] = arr[0];
let mut right = 0;
let mut max = 1;
for i in 1..arr.len() as i32 {
let mut l = 0;
let mut r = right;
while l <= r {
let mut m = (l + r) / 2;
if arr[i as usize] > ends[m as usize] {
l = m + 1;
} else {
r = m - 1;
}
}
right = get_max(right, l);
ends[l as usize] = arr[i as usize];
max = get_max(max, l + 1);
}
return max;
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// i : 当前来到的下标
// f、s、t : ends数组中放置的数字!
// ? == 0,没放!
// n : 一共的长度!
// m : 每一位,都可以在1~m中随意选择数字
// 返回值:i..... 有几个合法的数组!
fn zuo(i: i32, f: i32, s: i32, t: i32, n: i32, m: i32) -> i32 {
if i == n {
return if f != 0 && s != 0 && t != 0 { 1 } else { 0 };
}
// i < n
let mut ans = 0;
for cur in 1..=m {
if f == 0 || f >= cur {
ans += zuo(i + 1, cur, s, t, n, m);
} else if s == 0 || s >= cur {
ans += zuo(i + 1, f, cur, t, n, m);
} else if t == 0 || t >= cur {
ans += zuo(i + 1, f, s, cur, n, m);
}
}
return ans;
}
// 正式方法
// 需要看最长递增子序列!
// 尤其是理解ends数组的意义!
fn number2(n: i32, m: i32) -> i32 {
//repeat(vec![]).take((m+1) as usize).collect();
let mut dp: Vec<Vec<Vec<Vec<i32>>>> = repeat(
repeat(
repeat(repeat(-1).take((m + 1) as usize).collect())
.take((m + 1) as usize)
.collect(),
)
.take((m + 1) as usize)
.collect(),
)
.take(n as usize)
.collect();
return process2(0, 0, 0, 0, n, m, &mut dp);
}
fn process2(
i: i32,
f: i32,
s: i32,
t: i32,
n: i32,
m: i32,
dp: &mut Vec<Vec<Vec<Vec<i32>>>>,
) -> i32 {
if i == n {
return if f != 0 && s != 0 && t != 0 { 1 } else { 0 };
}
if dp[i as usize][f as usize][s as usize][t as usize] != -1 {
return dp[i as usize][f as usize][s as usize][t as usize];
}
let mut ans = 0;
for cur in 1..=m {
if f == 0 || cur <= f {
ans += process2(i + 1, cur, s, t, n, m, dp);
} else if s == 0 || cur <= s {
ans += process2(i + 1, f, cur, t, n, m, dp);
} else if t == 0 || cur <= t {
ans += process2(i + 1, f, s, cur, n, m, dp);
}
}
dp[i as usize][f as usize][s as usize][t as usize] = ans;
return ans;
}
相关文章
- Linux文件之strstr函数、将一个整数,结构体和结构体数组写进文件里
- 2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组, 求剩下的数组,严格连续递增的子数组最大长度。 n <= 10^6。 来自字节。
- 2022-09-07:给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如,序列 [4,6,16
- 2022-09-11:arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个“块”, 并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排
- java 输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组
- 2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。 你可以按 任意顺序 返回答案。
- php案例:创建一个数组cookie
- 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
- 2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组,求剩下的数组,严格连续递增的子数组最大长度。n
- c语言超出数组范围会怎样_有一个整型数组a,其中含有n个元素
- 2022-12-06:定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严格升序的情况下,得到的最大累加和
- 2022-12-16:给你一个长度为n的数组,并询问q次 每次询问区间[l,r]之间是否存在小于等于k个数的和大于等于x 每条查询返回true或者false。
- 2022-12-18:给定一个长度为n的二维数组graph,代表一张图, graph[i] = {a,b,c,d} 表示i讨厌(a,b,c,d),讨厌关系为双向
- 2022-11-04:给定一个正数n,表示有多少个节点给定一个二维数组edges,表示所有无向边edges[i] = {a, b
- 2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调,例如,数组为 nums = [2,4,1
- php数组函数序列之next()-移动数组内部指针到下一个元素的位置,并返回该元素值
- c语言动态数组示例
- js创建一个input数组并绑定click事件的方法