日本免费全黄少妇一区二区三区-高清无码一区二区三区四区-欧美中文字幕日韩在线观看-国产福利诱惑在线网站-国产中文字幕一区在线-亚洲欧美精品日韩一区-久久国产精品国产精品国产-国产精久久久久久一区二区三区-欧美亚洲国产精品久久久久

  1. 首頁 > 云知道 > >

M代表什么數(shù)字單位 m代表什么數(shù)字

云知道

2022-12-22：給定一個(gè)數(shù)字n，代表數(shù)組的長度，
給定一個(gè)數(shù)字m，代表數(shù)組每個(gè)位置都可以在1~m之間選擇數(shù)字，
所有長度為n的數(shù)組中，最長遞增子序列長度為3的數(shù)組，叫做達(dá)標(biāo)數(shù)組 。
返回達(dá)標(biāo)數(shù)組的數(shù)量 。
1 <= n <= 500，
1 <= m <= 10，
500 * 10 * 10 * 10，
結(jié)果對(duì)998244353取模，
實(shí)現(xiàn)的時(shí)候沒有取模的邏輯，因?yàn)榉侵攸c(diǎn) 。
來自微眾銀行 。
答案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!("出錯(cuò)了!");}}}println!("功能測試結(jié)束");}// 暴力方法// 為了驗(yàn)證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 }// i : 當(dāng)前來到的下標(biāo)// f、s、t : ends數(shù)組中放置的數(shù)字！// ? == 0，沒放！// n : 一共的長度！// m : 每一位 ， 都可以在1~m中隨意選擇數(shù)字// 返回值：i..... 有幾個(gè)合法的數(shù)組！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數(shù)組的意義！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代表什么數(shù)字單位 m代表什么數(shù)字


【M代表什么數(shù)字單位 m代表什么數(shù)字】

    推薦閱讀