题解

题面描述

多多有一本共 $n$ 页的书，每页读完会获取一定知识量 $a_i$。读书规则如下：

• 正常读：1分钟读1页，能完整得到该页的知识量 $a_i$。
• 使用能力：1分钟读连续2页，但这两页的知识量只能获得 $(a_i + a_{i+1})/2$。

多多只有 $m$ 分钟的时间来读完这 $n$ 页，如果无法读完则输出 $-1$，否则输出可以获得的最大知识量（保留一位小数）。

思路

我们希望在最少的（或恰好不超过 $m$）分钟内读完 $n$ 页，并使获得的知识量最大。
常用方法是 动态规划（DP）。定义状态如下：

• 令 $dp[i][t]$ 表示“在 $t$ 分钟内读完前 $i$ 页能获得的最大知识量”（如果无法在 $t$ 分钟内读完 $i$ 页，则记为不可行状态，比如用 $-\infty$ 或者某个标识表示）。

转移方程有两种读法对应两种状态转移：

1. 正常读：如果读第 $i$ 页时用1分钟，那么
   $dp[i][t] = max(dp[i][t],dp[i-1][t-1] + a_i)$
   前提是 $dp[i-1][t-1]$ 可行。

2. 使用能力：如果在1分钟内读第 $i-1$ 和第 $i$ 页，那么

   dp[i][t] = max(dp[i][t],dp[i-2][t-1] + ($a_{i-1}$ + $a_i$)/2)

   前提是 $dp[i-2][t-1]$ 可行。

初始条件：

• $dp[0][0] = 0$，表示0页用0分钟，知识量是0。
• 其他 $dp[i][0]$ (当 $i>0$) 应该是不可行的。

最终答案：

• 我们要看 $dp[n][t]$ 在 $t \le m$ 范围内的最大值，如果所有 $dp[n][t]$ 对 $t \le m$ 都不可行，则返回 $-1$；
• 否则返回最大值（保留一位小数）。

时间复杂度：

• $n$ 和 $m$ 均至多 1000，DP 循环复杂度大约 $O(n \times m)$，可以接受。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<double> a(n+1);
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }

    // 如果最大可能的页数(2*m)还读不完n页，则直接-1
    // 不过即使2*m >= n，也不一定能保证一定能在m分钟读完
    // 但若2*m < n，那么一定读不完
    if(2*m < n){
        cout << -1 << "\n";
        return 0;
    }

    // dp[i][t] 表示在 t 分钟内读完 i 页的最大知识量
    // 不可行时设置为 -1 表示无效
    static double dp[1001][1001];
    for(int i=0; i<=n; i++){
        for(int t=0; t<=m; t++){
            dp[i][t] = -1.0; // 初始不可行
        }
    }
    dp[0][0] = 0.0; // 0 页 0 分钟 知识量 = 0

    for(int i=1; i<=n; i++){
        for(int t=1; t<=m; t++){
            // 1) 正常读这一页(前提: 前面 i-1 页在 t-1 分钟可行)
            if(dp[i-1][t-1] >= 0){
                dp[i][t] = max(dp[i][t], dp[i-1][t-1] + a[i]);
            }
            // 2) 使用能力读两页(i-1, i一起读，前提: i>=2)
            if(i >= 2 && dp[i-2][t-1] >= 0){
                dp[i][t] = max(dp[i][t], dp[i-2][t-1] + (a[i-1] + a[i]) / 2.0);
            }
        }
    }

    // 在 t <= m 中寻找 dp[n][t] 的最大值
    double ans = -1.0;
    for(int t=1; t<=m; t++){
        ans = max(ans, dp[n][t]);
    }

    if(ans < 0){ // 不可行
        cout << -1 << "\n";
    } else {
        // 输出保留一位小数
        cout << fixed << setprecision(1) << ans << "\n";
    }

    return 0;
}

python

import sys

# 从标准输入读取所有内容后拆分
data = sys.stdin.read().strip().split()
# 前两个是 n 和 m，后面是 n 个 a_i
n, m = map(int, data[:2])
a = [0.0] + list(map(float, data[2:]))

# 如果最快(每分钟读2页)都无法读完 n 页，则直接输出 -1
if 2*m < n:
    print(-1)
    sys.exit(0)

# dp[i][t] 表示在 t 分钟内读完 i 页可获得的最大知识量
# 若不可行则用 -1.0 标记
dp = [[-1.0]*(m+1) for _ in range(n+1)]
dp[0][0] = 0.0  # 0 页 0 分钟，知识量为 0

# 开始进行动态规划
for i in range(1, n+1):
    for t in range(1, m+1):
        # 1) 用1分钟读1页
        if dp[i-1][t-1] >= 0:
            dp[i][t] = max(dp[i][t], dp[i-1][t-1] + a[i])
        # 2) 用1分钟读2页 (i-1, i)
        if i >= 2 and dp[i-2][t-1] >= 0:
            dp[i][t] = max(dp[i][t], dp[i-2][t-1] + (a[i-1] + a[i]) / 2.0)

# 从 dp[n][1..m] 中取最大值
ans = max(dp[n][1: m+1])

# 若依然是 -1.0 说明不可行，否则输出答案
if ans < 0:
    print(-1)
else:
    # 保留一位小数
    print(f"{ans:.1f}")

java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        double[] a = new double[n+1];
        for(int i=1; i<=n; i++){
            a[i] = sc.nextDouble();
        }
        
        // 若 2*m < n, 说明无法读完
        if(2*m < n){
            System.out.println(-1);
            return;
        }
        
        // dp[i][t] = 在 t 分钟内读完 i 页的最大知识量; 用 -1 表示不可行
        double[][] dp = new double[n+1][m+1];
        for(int i=0; i<=n; i++){
            Arrays.fill(dp[i], -1.0);
        }
        dp[0][0] = 0.0;
        
        for(int i=1; i<=n; i++){
            for(int t=1; t<=m; t++){
                // 1) 正常读1页
                if(dp[i-1][t-1] >= 0){
                    dp[i][t] = Math.max(dp[i][t], dp[i-1][t-1] + a[i]);
                }
                // 2) 使用能力读2页
                if(i >= 2 && dp[i-2][t-1] >= 0){
                    dp[i][t] = Math.max(dp[i][t], dp[i-2][t-1] + (a[i-1] + a[i]) / 2.0);
                }
            }
        }
        
        double ans = -1.0;
        for(int t=1; t<=m; t++){
            ans = Math.max(ans, dp[n][t]);
        }
        
        if(ans < 0){
            System.out.println(-1);
        } else {
            // 保留一位小数输出
            System.out.printf("%.1f\n", ans);
        }
    }
}

题目内容

多多很喜欢读书，现在多多有一本书，书有$n$页，每读完一页，多多都可以获得$ai$的知识量。正常情况下，多多每分钟可以读完一页，但是多多还有一个能力，可以在一分钟内读完连续两页的内容，只不过能获取的知识量只有正常读完两页知识量之和的二分之一。现在多多只有$m$分钟的时间用来读完这本书，请你告诉多多他最多可以获得多少的知识。

输入描述

输入两行

第一行包含两个整数$n$和$m(1<=n,m<=1000)$,表示书的页数和用来读书的时间。

第二行包含$n$个数字，每个数字$a_i(0<=ai<=10000)$表示第$i$页的知识量。

输出描述

输出一行，包含一个数字$ans$，表示最大可获取的知识量，输出的结果保留一位小数，如果在$m$分 钟内不能读完一本书，输出"$-1$"

补充说明

$50$的数据,$n<=100$

$100$的数据,$n<=1000,0<=ai<=10000,m<=n$

样例1

输入

4 1
1 2 3 4

输出

-1

样例2

输入

5 3
1 2 3 2 1

输出

6.0

说明

使用能力读完$1、2$两页，获取知识量$1.5$

第$3页$正常读,获取知识量$3$

使用能力读完$4、5$两页，获取知识量$1.5$

花费三分钟总计获得$6$的知识量