问题分析

吉他手在每首歌开始前改变音量，可以选择调高或调低给定的改变量。音量必须在 [0, maxLevel] 范围内。目标是找到演奏最后一首歌时的最大音量（即所有改变完成后），如果无法避免音量超出范围，则输出 -1。

关键点：

  • 初始状态：音量为 beginLevel。
  • 每次改变：对于给定的改变量 c_i，可以从当前音量 j 变为 j + c_i（调高）或 j - c_i（调低），但新音量必须在 [0, maxLevel] 内。
  • 目标：经过所有 n 次改变后，找到可达的最大音量。
  • 约束：n 最大为 50，maxLevel 最大为 1000，因此可以使用动态规划高效解决。

动态规划方法

使用一个布尔数组 dp，其中 dp[j] 表示音量 j 是否可达。数组大小为 maxLevel + 1（索引从 0 到 maxLevel）。

  • 初始化：dp[beginLevel] = true，其余为 false。
  • 迭代更新：对于每个改变量 c_i：
    • 创建新数组 next_dp，初始全 false。
    • 遍历所有音量 j（0 到 maxLevel），如果 dp[j] 为 true：
      • 如果 j - c_i >= 0，则设置 next_dp[j - c_i] = true（调低）。
      • 如果 j + c_i <= maxLevel，则设置 next_dp[j + c_i] = true（调高）。
    • 更新 dp = next_dp。
  • 结果提取：所有改变后，从高到低遍历 dp 数组，找到第一个 true 的音量即为最大音量；如果全 false，输出 -1。

该方法时间复杂度为 O(n * maxLevel)，在约束下可行。

代码实现

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,beginLevel,maxLevel;
    cin>>n>>beginLevel>>maxLevel;
    vector<int> c(n);
    for(int i = 0;i<n;i++)
    {
        cin>>c[i];
    }
    vector<vector<bool>> dp(n+1,vector<bool>(maxLevel+1,false));
    dp[0][beginLevel] = true;
    for(int i =1;i<=n;i++)
    {
        int current_c = c[i-1];
        for(int v = 0;v<=maxLevel;++v)
        {
            if(dp[i-1][v])
            {
                int new_v = v + current_c;
                if (new_v >= 0 && new_v <= maxLevel) {
                    dp[i][new_v] = true;
                }
                new_v = v - current_c;
                if (new_v >= 0 && new_v <= maxLevel) {
                    dp[i][new_v] = true;
                }
            }
        }
    }
    for (int v = maxLevel; v >= 0; --v) {
        if (dp[n][v]) {
            cout << v << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        string[] data = Console.ReadLine().Split();
        int n = int.Parse(data[0]);
        int beginLevel = int.Parse(data[1]);
        int maxLevel = int.Parse(data[2]);
        
        int[] c = Console.ReadLine().Split()
                     .Select(int.Parse)
                     .ToArray();
        
        // dp[j] 表示音量 j 是否可达
        bool[] dp = new bool[maxLevel + 1];
        dp[beginLevel] = true;
        
        foreach (int change in c)
        {
            bool[] nextDp = new bool[maxLevel + 1];
            
            for (int j = 0; j <= maxLevel; j++)
            {
                if (!dp[j]) continue;
                
                // 尝试调低音量
                if (j - change >= 0)
                    nextDp[j - change] = true;
                
                // 尝试调高音量
                if (j + change <= maxLevel)
                    nextDp[j + change] = true;
            }
            
            dp = nextDp;
        }
        
        // 从高到低寻找最大可达音量
        int maxVolume = -1;
        for (int j = maxLevel; j >= 0; j--)
        {
            if (dp[j])
            {
                maxVolume = j;
                break;
            }
        }
        
        Console.WriteLine(maxVolume != -1 ? maxVolume.ToString() : "-1");
    }
}

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
    
    n = int(data[0])
    beginLevel = int(data[1])
    maxLevel = int(data[2])
    c = list(map(int, data[3:3+n]))
    
    # dp[j] 表示音量 j 是否可达
    dp = [False] * (maxLevel + 1)
    dp[beginLevel] = True
    
    for change in c:
        next_dp = [False] * (maxLevel + 1)
        for j in range(maxLevel + 1):
            if dp[j]:
                low = j - change
                if low >= 0:
                    next_dp[low] = True
                high = j + change
                if high <= maxLevel:
                    next_dp[high] = True
        dp = next_dp
    
    # 从高到低找最大可达音量
    max_vol = -1
    for j in range(maxLevel, -1, -1):
        if dp[j]:
            max_vol = j
            break
    
    print(max_vol if max_vol != -1 else -1)

if __name__ == '__main__':
    main()