找到创建某一序列所需的最小对象数
您有N个字段(1 <= N <= 100)，它们都排列在一条长长的直线上。每个字段可能包含几种类型的音乐播放器；您拥有B类型的音乐播放器(1 <= B <= 20)，而类型I的音乐播放器的音量为V(i) (1 <= V(i) <= 100)。此外，路上还刮着强风，把音乐的声音吹向一个方向:如果某个领域的音乐音量是X，那么在下一个领域，这将贡献出X-1对音乐总量的贡献(以及之后领域中的X-2，等等)。但是，一旦它达到0，所贡献的卷就不会变成负值。
考虑到您在每个字段中录制的音乐数量，请计算您可能拥有的音乐播放器的最小数量。
您在任何字段中记录的卷最多为100,000卷。
输入格式：
- 第1行:整数N和B。
- 行2..1+B: i+1行包含整数V(i)。
- Line 2+B..1+B+N: Line 1+B+i包含字段i中所有呻吟的总音量。
样本输入：
5 2 5 7 0 17 16 20
输入详细信息:您拥有5个字段，记录的音量为0、17、16、20、19。有两种类型的音乐播放器；第一种是5卷，另一种是7卷。
输出格式：
- 第1行:您拥有的音乐播放器的最小数量，或者-1，如果没有与输入一致的音乐播放器的配置。
样本输出：
4.
产出详情：
领域2有2台1型音乐播放器和1台2型音乐播放器，4场中还有另一台type#1音乐播放器，总共有4台音乐播放器。这是在实地记录这些卷所需的最低限度。
我的想法:我理解这是一个动态规划问题。我当时以为dpi代表了第n个领域的音乐播放器，但我似乎不明白。
你能帮我解释一个很好的dp解决方案吗?如果可能的话，请提供一些psuedocode，这样我就可以更好地编码dp了。
回答 1
Stack Overflow用户
发布于 2014-03-10 04:01:40
不是最好的解决方案，而是使用动态规划解决时间复杂性O(B * MAX(recorded volume) + N)问题的解决方案。
这是一个两步的解决方案。在步骤1中，找到产生特定音量从1到最大值(录制的音量)所需的最小音乐播放器(可能有些卷不可用)。
然后在步骤2中，从第一个字段到最后一个字段，计算每个字段上需要生成的音量，然后使用步骤1中的结果来知道该领域需要多少音乐播放器。
以您的输入/输出为例。在步骤1中，您可以得到player_required5 = 1，player_required7 = 1，player_required10 = 2，player_required12 = 2，player_required14 = 2，player_required15 = 3，player_required17 = 3，player_required19 = 3，……。意味着你需要一个玩家生产5或7的音量，但如果你想生产15或17卷，你需要3名球员。
在第二步中，先到第一场，音量为0，不需要球员。在第二场，体积是17，所以你需要3名球员在这个领域。在第3场中，第2场的体积为16 (17-1)，与第3场的体积相当，因此第3场不需要球员，而在第4场，第3场的体积为15，而第3场的体积为20。所以你知道你应该在第4场产生5的音量，根据第1步的计算，这里需要一个玩家。第5场不需要任何球员。总之，你需要4个音乐播放器(第2场3名，第4场1名)
如果无法在第2步中的任何字段中生成所需的音量，则应该输出-1，因为没有与输入相一致的音乐播放器的配置。
对不起英语不好，希望它能帮上忙。
https://stackoverflow.com/questions/22288490
复制相似问题
腾讯云开发者
