13. 云南菌子加工[200分]

题目内容

云南的菌子加工厂要加工一批野生菌，所有菌子同时进厂。由于菌子新鲜度随时间流失，价值不断衰减。工厂不能同时加工菌子，即逐个串行加工，正在加工的菌子价值不再衰减，加工完毕立即售卖。已知每个菌子的初始市场价值和新鲜度衰减速度（每小时损失的价值），菌子的实际价值 = 初始价值 - 衰减速度 × 从进入工厂到开始加工的等待时间。在给定时间内，合理安排加工顺序使得加工完成的菌子总价值最大化。

每个菌子的加工时间固定为 5 小时，加工所有菌子的总耗时不能超过给定的总加工时间。若菌子的实际价值衰减至零或负值，则不能再售卖，即不需要参与加工。

输入描述

两个整数 count 和 total，count 表示菌子数量（1 ≤ count ≤ 15），total 表示可用的总加工时间（5 ≤ total ≤ 75，单位：小时）。

• 整型数组 values，values[i] 表示第 i 个菌子的初始市场价值，单位：元，共 count 个整数。
• 整型数组 decays，decays[i] 表示第 i 个菌子的衰减速度，单位：元/小时，共 count 个整数。

输出描述

输出一个整数，表示在给定时间内能加工完成的菌子的最大总价值。

样例

样例 1

输入

3 15
10 8 6
0 0 0

输出

24

说明： 总加工时间 15 足够加工全部 3 个菌子，由于菌子无衰减，依次等待 0/5/10 小时，总价值为 10+8+6=24。虽然也可调换菌子加工顺序，但结果仍是 24。

样例 2

输入

3 20
20 10 15
3 1 2

输出

25

说明：

• 由于菌子不断衰减，先选择菌 1 加工，价值 20
• 再加工菌 3，等待 5 小时，实际价值 =15-2×5=5
• 最后加工菌 2，等待 10 小时，实际价值 =10-1×10=0，菌子不能再售卖，放弃加工

总价值 25。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const inputs = [];
rl.on('line', (input) => {
    inputs.push(input);
})
rl.on('close', () => {
    const count = inputs[0].split(' ').map(Number)[0];
    const total = inputs[0].split(' ').map(Number)[1];
    const values = inputs[1].split(' ').map(Number);
    const decays = inputs[2].split(' ').map(Number);
    let used = Array(count).fill(false);
    let max = 0;
    const canCount = Math.floor(total/5) > count ? count : Math.floor(total/5);
    // console.log(count, total, values, decays)
    const dfs = (n, count, money) => {
        const v = values[n] - decays[n] * (count - 1) * 5;
        money += (v > 0 ? v : 0);
        used[n] = true;
        if (count === canCount) {
            // console.log(used, money);
            max = Math.max(max, money);
            return;
        }
        ++count;
        for(let i=0; i<values.length; i++) {
            if (!used[i]) {
                used[i] = true;
                dfs(i, count, money);
                used[i] = false;
            }
        }
        --count;
        used[n] = false;
    }
    for(let i=0; i<values.length; i++) {
        dfs(i, 1, 0);
    }
    console.log(max);
})