首页 > [HAOI2012]音量调节
开通博客写题解
头像 hnust_yangyanjun
发表于 2021-04-19 18:29:12
题意：有一个歌手要唱n首歌，每首歌在唱之前可以调节ci的音量,上调或者下调，但不能低于0或者高于maxLevel，初始音量为beginLevel，求最后一首歌音量最大为多少，如果不能满足规则，则输出-1. 思路：首先观察数据范围，我们发现n和maxLevel都不是很大，所有我们可以使用dp来写. 定 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-04-13 10:59:13
Solution 转移方程比较简单，这里就直接给出了。代表第首歌结束的时候是的音量，并且可以满足前面首歌都不低于0和不大于的条件。 初始条件就是。 转移方程就是下面给出的，注意不要越界了。 状态总数，转移时间复杂度，空间复杂度。 解决之后考虑如何做下优化吧，第一步首先知道对于第个物品可以更新的状态 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Stjp20080714
发表于 2021-10-04 20:54:13
一个入门的背包 但是区别于普通的背包，这个背包可以同时加（或者）减。 解决方案: 改写dp方程 考虑 f[i]f[i]f[i] 的来源 只要其中一个可以，那么 f[i][j]f[i][j]f[i][j] 也可以 接下来就是一些特判了 同时不难发现 f[i]f[i]f[i] 只与 f[i−1]f[i- 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客956500257号
发表于 2021-08-30 13:08:20
对于%60的数据，递归是个简单又容易理解的方法。初学者可用此法：思路：每次递归有两种情况：加或减。即： solve(curLevel + a[t], t + 1);或 solve(curLevel - a[t], t + 1); #include <cstdio> #include &l 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 昵称很长很长真是太好了
发表于 2021-04-13 22:18:35
题解：简单的dp。也许dp我只会做这种小白型的了（剩下的交给队友奥里给）首先我们先看一下，不优化空间的dp怎么写的。 我们发现他最多会演唱50首歌曲，最大音调为1000。开一个代表演唱到第i个物品的时候，能不能演唱出来音调为j的歌曲。初始状态全是false，只有转移方程： 代码： #include 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 双子远足
发表于 2019-09-10 14:30:36
经典背包问题，字符串问题心得：很多题都是背包问题的翻版，但怎么缕清楚思路是需要慢慢培养的，不能一上来就套用动态规划，这样往往会出现方向错误。具体到这道题：可以找到一个状态变量，那就是第i首歌曲所可以达到的所有可能到达的音量，用dp[i][t]的bool变量表示。t的范围是0~maxLevel,这样我 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 yanchengzhi
发表于 2020-02-16 16:13:32
链接：https://ac.nowcoder.com/acm/problem/19990 来源：牛客网 题目描述 一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 牛客424309211号
发表于 2024-04-10 09:38:10
/* 该问题可转化为01背包的二维数组(数据较少可用)，一维滚动数组不好操作 1.dp数组含义 dp[i][j]表示第i首歌时，j为其音量大小，如果0<=j<=maxLevel,则令dp[i][j]=1，否则为0 2.递推公式---当前音量共两种情况，之前一首歌的音量加或减列表中要改 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-04-13 18:07:24
做法：dp 思路： 因为音量范围在0~maxx之间并且maxx<=1000，所以我们设dp[i][j]为第i次音量变化后此时音量为j的方案是否存在 在符合条件的音量内进行转移 和 代码 // Problem: [HAOI2012]音量调节 // Contest: NowCoder // URL 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 谁与语冰
发表于 2023-04-17 16:09:43
#include<iostream> using namespace std; int n,b,m,maxn=-1; int p[110]; bool dp[110][1100]; int main() { cin>>n>>b>>m; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”