[HAOI2012]音量调节

[HAOI2012]音量调节

https://ac.nowcoder.com/acm/problem/19990

题号 NC19990
名称 [HAOI2012]音量调节
来源 [HAOI2012]

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量,所以他决定每一首歌之前他都要改变一次音量。在演出开始之前,他已经做好了一个列表,里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量,他可以选择调高也可以调低。

音量用一个整数描述。输入文件中给定整数beginLevel,代表吉他刚开始的音量,以及整数maxLevel,代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn,表示在第i首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌,你的任务是找到这个最大音量是多少。

样例

输入
3 5 10               
5 3 7
输出
10

备注:

算法

(dp)

先观察数据范围 提醒我们可以用动态规划


状态表示:用 表示执行完前次音量调整操作后当前音量为的状态是否能达到(维护Boolean值)

状态计算:

​ 初值:

​ 中间状态: (从执行完前次操作后音量为 的状态 加上 转移过来)

(从执行完前次操作后音量为 的状态 减去 转移过来)


枚举到找到第一个,输出,否则输出-1

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 60,M = 1010;
const int INF = 0x3f3f3f3f;
bool f[N][M];
int n,s,m;

int main()
{
    scanf("%d%d%d",&n,&s,&m);
    f[0][s] = true;
    for(int i = 1;i <= n;i ++)
    {
        int c;
        scanf("%d",&c);
        for(int j = 0;j <= m;j ++)
        {
            if(j >= c) f[i][j] |= f[i - 1][j - c];
            if(j + c <= m) f[i][j] |= f[i - 1][j + c];
        }
    }
    for(int i = m;i >= 0;i --)
        if(f[n][i])
        {
            printf("%d\n",i);
            return 0;
        }
    printf("-1\n");
    return 0;
}
全部评论

相关推荐

06-25 09:33
厦门大学 Java
球球别拷打俺了:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司10个岗位
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-23 14:10
柴子木:找个工作你还发上脾气了🤣
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务