ly 在战场凹分，没吃午饭，饥肠辘辘的他从文具盒里翻出了一袋饼干...... 这袋饼干有 n 块，分别称作第 1,2...n 块，第 i 块饼干能提供 w [i] 的饱腹感. 有强迫症的 ly 必须从第 1 块开始吃，然后第 2 块... 直到总饱腹感达到（大于或等于）s 时即停止. 众所周知，万事万物都会随着多种因素的变化而变化，当然 ly 的饱腹感上限 s 也不例外 于是 ly 会询问你 q 次：当他的饱腹感上限为 s [i] 时，他需要吃多少块饼干

这是一个典型的背包问题，可以使用动态规划来解决。

定义一个二维数组dp[i][j]，表示当饱腹感上限为j时，前i块饼干最多能提供多少饱腹感。

状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+w[i])

其中，dp[i-1][j]表示不选第i块饼干，dp[i-1][j-w[i]]+w[i]表示选第i块饼干。

最终的答案是最小的满足dp[n][j]>=s[i]的j。

具体实现可以参考以下代码（Python）：

n = int(input())
w = list(map(int, input().split()))

max_s = 1000000
dp = [[0]*(max_s+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, max_s+1):
        dp[i][j] = dp[i-1][j]
        if j >= w[i-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+w[i-1])

q = int(input())
for i in range(q):
    s = int(input())
    j = 1
    while dp[n][j] < s:
        j += 1
    print(j)

时间复杂度为O(n*max_s+q)，可以通过本题。

相关问题

predefined-guitar-fretboards.ly里定义的和弦名称有哪些？

在 `predefined-guitar-fretboards.ly` 文件中，定义了以下吉他和弦名称：

- C
- Cm
- C7
- Cm7
- Cmaj7
- Csus4
- Cadd9
- C5
- C6
- Cm6
- C9
- Cm9
- C11
- C13
- C7sus4
- C7#5
- C7b5
- C7b9
- C7#9
- Cmaj7#5
- Cmaj7b5
- Cmaj9
- Cmaj11
- Cmaj13
- CmMaj7
- Cm6Maj7
- Cm7b5
- Cdim
- Cdim7
- Caug
- Caug7

java.util.LinkedHashMap cannot be cast to com.ly.cloud.sourceright.dto.SubmitDTO

根据提供的引用内容，报错"java.util.LinkedHashMap cannot be cast to com.ly.cloud.sourceright.dto.SubmitDTO"是因为在将JSON字符串转换为FdcpRes对象时，出现了类型转换错误。具体来说，将LinkedHashMap类型的对象转换为SubmitDTO类型的对象时发生了错误。

解决这个问题的方法是，确保在将JSON字符串转换为FdcpRes对象时，使用正确的类型转换方法。可以使用Jackson库来进行JSON字符串和Java对象之间的转换。以下是一个示例代码：

import com.fasterxml.jackson.databind.ObjectMapper;

// 将JSON字符串转换为FdcpRes对象
String json = "{\"list\": [1, 2, 3]}"; // 假设这是一个包含List属性的JSON字符串
ObjectMapper objectMapper = new ObjectMapper();
FdcpRes fdcpRes = objectMapper.readValue(json, FdcpRes.class);

// 获取List属性并进行类型转换
List<SubmitDTO> submitList = (List<SubmitDTO>) fdcpRes.getList();

在上面的代码中，首先使用ObjectMapper类将JSON字符串转换为FdcpRes对象。然后，通过getList()方法获取List属性，并将其强制转换为SubmitDTO类型的List。

请注意，确保FdcpRes类和SubmitDTO类正确定义，并且在代码中进行了正确的导入。