首页 > 试题广场 >

放它一马

[编程题]放它一马

热度指数：2663 时间限制：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

输出

说明

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

算法知识视频讲解

YUANDK

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] monsters = new int[n];
        for (int i = 0; i < n; i++) {
            monsters[i] = in.nextInt();
        }
        System.out.println(solution(monsters));
    }

    private static long solution(int[] monsters) {
        int n = monsters.length;
        if (n == 0) return 0;
        long max = 0;
        long[][] dp = new long[n + 1][10]; // 第二维大小为 n+1

        for (int i = 1; i <= n; i++) {
            int ai = monsters[i - 1];
            for (int j = 0; j <= i && j < 10; j++) {
                // 放走第i只获得的总经验
                long expSkip = dp[i - 1][j] + i;
                // 击杀第i只获得的总经验
                long combo = j + 1;
                long expGain = dp[i - 1][j - 1 < 0 ? 9 : j - 1] + ai * combo;
                dp[i][j] = Math.max(expSkip, expGain);
                if (max < dp[i][j]) max = dp[i][j];
            }
        }
        return max;
    }
}

发表于 2025-08-25 19:05:11 回复(0)

小小

题解 | #放它一马#

发表于 2025-08-11 22:35:40 回复(0)

小支支

c++版本的
#include <climits>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
int n;
while (cin >> n) {
vector<int> ex(n, 0);
for (int i = 0; i < n; i++) {
cin >> ex[i];
}
vector<vector<long>> dp(n + 1, vector<long>(10, 0));
for (int i = 0; i <= 9; i++) {
dp[0][i] = LONG_MIN;
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int k = 0; k <= 9; k++) {
if (k == 0) {
dp[i][k] = max(dp[i - 1][k] + i , dp[i - 1][9] + ex[i-1] + k * ex[i-1]);
} else {
dp[i][k] = max(dp[i - 1][k] + i , dp[i - 1][k - 1] + ex[i-1] + k * ex[i-1]);
}
}
}
long ans = 0;
for (int i = 0; i <= 9; i++) {
ans = max(ans, dp[n][i]);
}
// for (int i = 0; i <= n; i++) {
// for (int j = 0; j <= 9; j++) {
// cout<<i<<" "<<j<<"="" "<<dp[i][j]<<endl;="" }=""

cout="" <<="" ans="" endl;

}

发表于 2025-09-04 20:48:11 回复(0)

牛客192737559号

想得太简单了用的最简单的贪心模型，一步步算，但是就是算不对，还得是动态规划

发表于 2025-09-21 01:16:30 回复(0)

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)

提交观点

问题信息

动态规划数组

难度：

5条回答 86收藏 429浏览

放它一马

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题