2023-01-10：智能机器人要坐专用电梯把货物送到指定地点， 整栋楼只有一部电梯，并且由于容量限制智能机器人只能放下一件货物， 给定K个货物，每个货物都有所

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

contract Hello{

    function main() public pure returns (int32){
		int32 k = 3;
		int32[] memory from = new int32[](uint32(k));
		from[0] = 1;
		from[1] = 3;
		from[2] = 6;
		// from[3] = 5;
		// from[4] = 7;
		int32[] memory to = new int32[](uint32(k));
		to[0] = 4;
		to[1] = 6;
		to[2] = 3;
		// to[3] = 2;
		// to[4] = 8;
		int32 ans = minCost2(k,from,to);

		return ans;
    }

    // 正式方法
	function minCost2(int32 k, int32[] memory from, int32[] memory to) public pure returns (int32){
		int32 m = leftk(k);
		int32[][] memory dp = new int32[][](uint32(m));
		for (int32 i = 0; i < m; i++) {
			dp[uint32(i)]=new int32[](uint32(k));
			for (int32 j = 0; j < k; j++) {
				dp[uint32(i)][uint32(j)] = -1;
			}
		}
		return f(0, 0, k, from, to, dp);
	}

	function leftk(int32 k) public pure returns (int32){
		int32 ans = 1;
		while (k>0){
			ans*=2;
			k--;
		}
		return ans;
	}

	// 2^16 = 65536 * 16 = 1048576
	// 1048576 * 16 = 16777216
	function f(int32 status, int32 i, int32 k, int32[] memory from, int32[] memory to, int32[][] memory dp) public pure returns (int32){
		if (dp[uint32(status)][uint32(i)] != -1) {
			return dp[uint32(status)][uint32(i)];
		}
		int32 ans = 2147483647;
		if (status == leftk(k) - 1) {
			ans = to[uint32(i)] - 1;
		} else {
			for (int32 j = 0; j < k; j++) {
				if ((status & leftk(j)) == 0) {
					int32 t = 0;
					if(status == 0){
						t=1;
					}else{
						t = to[uint32(i)];
					}
					int32 come = abs(from[uint32(j)] - t);
					int32 deliver = abs(to[uint32(j)] - from[uint32(j)]);
					int32 next = f(status | leftk(j), j, k, from, to, dp);
					ans = min(ans, come + deliver + next);
				}
			}
		}
		dp[uint32(status)][uint32(i)] = ans;
		return ans;
	}

	function abs(int32 a)public pure returns (int32){
		if(a<0){
			return -a;
		}else{
			return a;
		}
	}

	function min(int32 a,int32 b)public pure returns (int32){
		if(a<b){
			return a;
		}else{
			return b;
		}
	}

}

use rand::Rng;
use std::iter::repeat;
fn main() {
    let k = 3;
    let mut from = vec![1, 3, 6];
    let mut to = vec![4, 6, 3];
    let ans1 = min_cost1(k, &mut from, &mut to);
    let ans2 = min_cost2(k, &mut from, &mut to);
    println!("ans1 = {}", ans1);
    println!("ans2 = {}", ans2);

    let k = 5;
    let mut from = vec![1, 3, 6, 5, 7];
    let mut to = vec![4, 6, 3, 2, 8];
    let ans1 = min_cost1(k, &mut from, &mut to);
    let ans2 = min_cost2(k, &mut from, &mut to);
    println!("ans1 = {}", ans1);
    println!("ans2 = {}", ans2);

    let nn: i32 = 8;
    let vv: i32 = 100;
    let test_time: i32 = 5000;
    println!("测试开始");
    for i in 0..test_time {
        let k = rand::thread_rng().gen_range(0, nn) + 1;
        let mut from = random_array(k, vv);
        let mut to = random_array(k, vv);
        let ans1 = min_cost1(k, &mut from, &mut to);
        let ans2 = min_cost2(k, &mut from, &mut to);
        if ans1 != ans2 {
            println!("出错了!{}", i);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

// 0 1 2
// from = {3, 6, 2}
// to = {7, 9, 1}
// from[i] : 第i件货，在哪个楼层拿货，固定
// to[i] : 第i件货，去哪个楼层送货，固定
// k : 一共有几件货，固定
// status : 00110110
// last : 在送过的货里，最后送的是第几号货物
// 返回值: 送完的货，由status代表，
// 而且last是送完的货里的最后一件，后续所有没送过的货都送完，
// 最后回到第一层，返回最小耗时
// k = 7
// status = 01111111
// 0000000000001
// 0000010000000 -1
// 0000001111111
fn zuo(status: i32, last: i32, k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {
    if status == (1 << k) - 1 {
        // 所有货送完了，回到1层去了
        return to[last as usize] - 1;
    } else {
        // 不是所有货都送完！
        let mut ans = i32::MAX;
        for cur in 0..k {
            // status : 0010110
            //            1
            if (status & (1 << cur)) == 0 {
                // 当前cur号的货物，可以去尝试
                // to[last]
                //    cur号的货，to[last] -> from[cur]
                let come = abs(to[last as usize] - from[cur as usize]);
                let delive = abs(to[cur as usize] - from[cur as usize]);
                let next = zuo(status | (1 << cur), cur, k, from, to);
                let cur_ans = come + delive + next;
                ans = get_min(ans, cur_ans);
            }
        }
        return ans;
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

fn abs(a: i32) -> i32 {
    if a < 0 {
        -a
    } else {
        a
    }
}

// 暴力方法
// 全排序代码
fn min_cost1(k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {
    return process(0, k, from, to);
}

fn process(i: i32, k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {
    if i == k {
        let mut ans = 0;
        let mut cur = 1;
        for j in 0..k {
            ans += abs(from[j as usize] - cur);
            ans += abs(to[j as usize] - from[j as usize]);
            cur = to[j as usize];
        }
        return ans + cur - 1;
    } else {
        let mut ans = i32::MAX;
        for j in i..k {
            swap(from, to, i, j);
            ans = get_min(ans, process(i + 1, k, from, to));
            swap(from, to, i, j);
        }
        return ans;
    }
}

fn swap(from: &mut Vec<i32>, to: &mut Vec<i32>, i: i32, j: i32) {
    let tmp = from[i as usize];
    from[i as usize] = from[j as usize];
    from[j as usize] = tmp;
    let tmp = to[i as usize];
    to[i as usize] = to[j as usize];
    to[j as usize] = tmp;
}

// 正式方法
fn min_cost2(k: i32, from: &mut Vec<i32>, to: &mut Vec<i32>) -> i32 {
    let m = 1 << k;
    let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take(k as usize).collect())
        .take(m as usize)
        .collect();
    return f(0, 0, k, from, to, &mut dp);
}

// 2^16 = 65536 * 16 = 1048576
// 1048576 * 16 = 16777216
fn f(
    status: i32,
    i: i32,
    k: i32,
    from: &mut Vec<i32>,
    to: &mut Vec<i32>,
    dp: &mut Vec<Vec<i32>>,
) -> i32 {
    if dp[status as usize][i as usize] != -1 {
        return dp[status as usize][i as usize];
    }
    let mut ans = i32::MAX;
    if status == (1 << k) - 1 {
        ans = to[i as usize] - 1;
    } else {
        for j in 0..k {
            if (status & (1 << j)) == 0 {
                let come = abs(from[j as usize] - if status == 0 { 1 } else { to[i as usize] });
                let deliver = abs(to[j as usize] - from[j as usize]);
                let next = f(status | (1 << j), j, k, from, to, dp);
                ans = get_min(ans, come + deliver + next);
            }
        }
    }
    dp[status as usize][i as usize] = ans;
    return ans;
}

fn random_array(n: i32, v: i32) -> Vec<i32> {
    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();
    for i in 0..n {
        ans[i as usize] = rand::thread_rng().gen_range(0, v) + 1;
    }
    return ans;
}