首页 > 试题广场 >

放它一马

[编程题]放它一马

热度指数：2860 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小美会按照编号从小到大的顺序依次遇到 $n$ 只怪物（编号为 $1 \sim n$ ），怪物 $i(1 \leqq i \leqq n)$ 的生命为 $a_i$ 。

$\hspace{15pt}$ 对于每只怪物，小美都可以选择放走Ta或者击败Ta。
$\hspace{23pt}\bullet\,$ 如果放走怪物，小美将获得 $i$ 点经验值。
$\hspace{23pt}\bullet\,$ 如果击败怪物，小美将获得 $a_i$ 点经验值，同时将额外获得 $(x \operatorname{mod} 10) \times a_i$ 点经验值， $x$ 为击败怪物数量（包括这一个怪物）。

$\hspace{15pt}$ 求小美最多可以从这 $n$ 个怪物中获得的经验值。

输入描述:

第一行输入一个整数  表示怪物数。
第二行输入  个整数  表示怪物的生命。

输出描述:

输出一个整数表示小美可以获得最高的经验值。

示例1

输入

3
5 3 2

输出

说明

第一个怪物选择击败获得 的经验值，第二个怪物选择击败获得  的经验值，第三只怪物选择击败获得  的经验值，总共获得  的经验值。

算法知识视频讲解

JavaScript

TimothyYin

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const ins = []

rl.on('line', function (line) {
    ins.push(line.trim())
});

rl.on('close', () => {
    const n = Number(ins[0])
    const a = ins[1].split(' ').map(Number)

    let dp = Array(10).fill(0)

    for (let i = n - 1; i >= 0; i--) {
        const hp = a[i]
        const mobId = i + 1
        const next = Array(10).fill(0)

        for (let r = 0; r < 10; r++) {
            // skip
            const skip = mobId + dp[r]
            // kill
            const mult = 1 + ((r + 1) % 10)
            const kill = hp * mult + dp[(r + 1) % 10]

            next[r] = skip > kill ? skip : kill
        }

        dp = next
    }

    console.log(dp[0])
})

发表于 2025-10-11 17:57:35 回复(0)