m代表什么数字(M代表什么数字单位)
2024-01-29 22:03 来源:网络 点击:
m代表什么数字(M代表什么数字单位)
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= 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 { 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 { if arr.len() == 0 { return 0; } let mut ends: Vec= 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 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(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>>> = 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 { 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; }
相关标签:
-
- 梦幻西游临时符(梦幻西游临时符有效期)
-
2024-01-29 22:01:37
-
- 小木槿的养殖方法和注意事项(木槿花叶子发黄是怎么回事)
-
2024-01-29 21:59:22
-
- 虾仁饺子的做法(宝宝吃虾仁饺子的做法)
-
2024-01-29 21:57:07
-
- giulia怎么读(giglio怎么读)
-
2024-01-29 10:24:16
-
- 红茶与绿茶的区别有哪些()(生茶和熟茶的区别)
-
2024-01-29 10:22:02
-
- 芳华是什么年龄(韶华指多大年龄)
-
2024-01-29 10:19:47
-
- 什么得妙填词语(什么得妙填动词)
-
2024-01-29 10:17:32
-
- 张起灵下跪的血尸是谁(阿宁变成了蛇母)
-
2024-01-29 10:15:17
-
- 中国移动异地补办最新(中国移动补卡异地)
-
2024-01-29 10:13:03
-
- 八角亭迷雾结局(八角亭迷雾结局什么意思)
-
2024-01-29 10:10:48
-
- 杨洋身高(杨洋身高体重个人资料)
-
2024-01-29 10:08:33
-
- 西秦是哪个朝代(西秦国都在哪里)
-
2024-01-29 10:06:19
-
- 三星发布会2020年时间(三星发布会时间在几月)
-
2024-01-29 10:04:04
-
- 感恩母亲的优美句子(感恩母爱的唯美句子)
-
2024-01-27 23:34:55
-
- word文档如何编辑目录
-
2024-01-27 23:32:41
-
- lol巨魔之王教程(LOL11.17巨魔之王 特朗德尔攻略)
-
2024-01-27 23:30:26
-
- 怎样打出特殊符号 这几种方法你一定要知道
-
2024-01-27 23:28:11
-
- 浦公英冶疗什么病 内服加外用可以治疗多种疾病
-
2024-01-27 23:25:57
-
- 年糕怎么炸?做法来了,快试试吧!
-
2024-01-27 23:23:42
-
- 每日一字:可怎么读
-
2024-01-27 23:21:27