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<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 < nlet 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;}

【M代表什么数字单位 m代表什么数字】

M代表什么数字单位 m代表什么数字

推荐阅读

Excel如何做出老板喜欢的统计表格？解决方法分享

专业技术资格证书与执业证书区别

屏风的作用有哪些

喝汤烫到舌头怎么办喝汤的温度多少合适

10大品牌洗衣机洗衣机十大品牌排名

丁姓100分以上的女孩名字，女孩姓丁取名字

dnf暴击堆到多少

粘水管漏水的胶带叫什么

人生日历有什么功能人生日历安卓版使用图文教程

种植小型西瓜怎么施足基肥

驴肉火烧生意怎么样,在街头摆摊卖驴肉火烧

有升号的谱子怎么弹升号4怎么弹吉他

金渐层猫该如何挑选？英短金渐层怎么挑选

弹弹堂3 工厂怎么打,任天堂推出新版3DS

梦见朋友被打了是什么意思

小编分享edge浏览器工具栏上的主页按钮如何删除