2022-04-20: the small regiment goes to participate in the military training. The military training is coming to an end. The officer wants to divide n people in a row into m groups, and then ask each g

2022-04-20： Small regiments go to military training , Military training is coming to an end ,
Sir wants to put everyone in a row n Personal share m Group , Then let each group go to the parade ceremony ,
Only one group of adjacent people can be selected , You can't change the position of people in the team at will ,
Scores will be given at the military parade , One of the strange deduction points is the maximum difference between each group ,
That is, the maximum value of each group minus the minimum value ,
Sir wants this to be divided into m Minimum total deduction component , Is this m The sum of the range difference of each group is the smallest .
The officer is thinking about how to arrange , Let Xiaotuan help him .

answer 2022-04-20：

Dynamic programming .
Time complexity ：O(M * N * N).

The code to use rust To write . The code is as follows ：

use rand::Rng;

fn main() {
    
    let mut arr: Vec<isize> = vec![];
    let n = rand::thread_rng().gen_range(10, 30);
    println!("n = {}", n);
    for i in 0..n {
    
        arr.push(rand::thread_rng().gen_range(1, 1000));
    }
    println!("arr = {:?}", arr);
    let m = rand::thread_rng().gen_range(1, n);
    println!("m = {}", m);
    let ret = min_score2(&mut arr, m);
    println!("ret = {}", ret);
}

fn min_score2(arr: &mut Vec<isize>, m: isize) -> isize {
    
    if m == 0 {
    
        return 0;
    }
    let n: isize = arr.len() as isize;
    let mut score: Vec<Vec<isize>> = vec![];
    for i in 0..n {
    
        score.push(vec![]);
        for j in 0..n {
    
            score[i as usize].push(0);
        }
    }
    for i in 0..n {
    
        let mut max = arr[i as usize];
        let mut min = arr[i as usize];
        score[i as usize][i as usize] = max - min;
        for j in i + 1..n {
    
            max = get_max(max, arr[j as usize]);
            min = get_min(min, arr[j as usize]);
            score[i as usize][j as usize] = max - min;
        }
    }
    let mut dp: Vec<Vec<isize>> = vec![];
    for i in 0..m + 1 {
    
        dp.push(vec![]);
        for j in 0..n {
    
            dp[i as usize].push(0);
        }
    }
    for i in 0..n {
    
        dp[1][i as usize] = score[0][i as usize];
    }
    for split in 2..=m {
    
        for i in split..n {
    
            dp[split as usize][i as usize] = dp[(split - 1) as usize][i as usize];
            for j in 1..=i {
    
                dp[split as usize][i as usize] = get_min(
                    dp[split as usize][i as usize],
                    dp[(split - 1) as usize][(j - 1) as usize] + score[j as usize][i as usize],
                );
            }
        }
    }
    //println!("dp = {:?}", dp);
    return dp[m as usize][(n - 1) as usize];
}

fn get_max(a: isize, b: isize) -> isize {
    
    if a > b {
    
        a
    } else {
    
        b
    }
}

fn get_min(a: isize, b: isize) -> isize {
    
    if a < b {
    
        a
    } else {
    
        b
    }
}

The results are as follows ：

Zuo Shen java Code