亚历克斯的无聊游戏 | 动态规划

server/2024/11/19 20:49:39/

描述

亚历克斯不喜欢无聊。这就是为什么每当他感到无聊时,他都会想出一些游戏。一个漫长的冬夜,他想出了一个游戏

给定由n个整数组成的序列a。玩家可以选择其中的整数。在一个步骤中,他可以选择序列中的一个元素(让我们把它表示为a[k]),然后删除它,此时a中所有值等于a[k]+ 1和a[k]- 1的元素也必须从序列中删除。这一步为玩家带来a[k]分数。

亚历克斯应该怎样选择,才能在游戏中得到的分数最多?

输入

输入一个t表示t个测试用例。

对于每个测试用例,输入一个整数n表示a中有n个整数。

接下来输入n个整数

输出

对于每个测试用例,输出一个整数表示可以得到的多分数。末行有换行

样例解析,有一个测试用例,包含7个整数的序列,选择3 5 7, 删除所有2,4,得到:

3×2+5+7=18

输入样例 1 

1
7
5 3 4 2 3 7 2

输出样例 1

18

题解:

        使用动态规划,map的作用是记录出现过的数以及出现的次数。DP[i]的意思是从0到i中,在数组中出现过的数能到达的最大的分数。

        状态转移方程:

DP[i]=max(DP[i-1],DP[i-2]+map[i]*i)

        解释以下就是,要不选择前两个的最值加上自己,要不就不加自己之后的最大值。并且DP必须每个数都遍历过去,因为map只记录数值不记录数与数之间的关系。

代码:

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;int t=0,n=0,i=0,j=0,num=0,maxn=0;
map<int ,int > mp;
map<int ,int >::iterator it;
ll dp[10001]={0};main(){cin >> t;while(t>0){mp.clear();cin >> n;maxn=0;for(i=0;i<n;i++){cin >> num;if(num>maxn){maxn=num;}mp[num]++;}dp[0]=0;//cout << dp[0] << "\n";dp[1]=mp[1];//cout << dp[1] << "\n";for(i=2;i<=maxn;i++){dp[i]=max(dp[i-1],dp[i-2]+mp[i]*i);}cout << dp[maxn] << "\n";t--;}
}


http://www.ppmy.cn/server/143295.html

相关文章

Python高级编程模式和设计模式

一 装饰器模式 order_sources:source1:on_agreement: "reduce_receivable"on_completion: "reduce_receivable"on_rejection: "none"source2:on_agreement: "none"on_completion: "reduce_receivable"on_rejection: "…

无插件H5播放器EasyPlayer.js网页web无插件播放器选择全屏时,视频区域并没有全屏问题的解决方案

EasyPlayer.js H5播放器&#xff0c;是一款能够同时支持HTTP、HTTP-FLV、HLS&#xff08;m3u8&#xff09;、WS、WEBRTC、FMP4视频直播与视频点播等多种协议&#xff0c;支持H.264、H.265、AAC、G711A、MP3等多种音视频编码格式&#xff0c;支持MSE、WASM、WebCodec等多种解码方…

大模型(LLMs)RAG 版面分析——表格识别方法篇

大模型&#xff08;LLMs&#xff09;RAG 版面分析——表格识别方法篇 一、为什么需要识别表格&#xff1f; 表格的尺寸、类型和样式展现出多样化的特征&#xff0c;如背景填充的差异性、行列合并方法的多样性以及内容文本类型的不一致性等。同时&#xff0c;现有的文档资料不…

计算机编程中的异步编程模型及其在提升应用响应性中的作用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 计算机编程中的异步编程模型及其在提升应用响应性中的作用 计算机编程中的异步编程模型及其在提升应用响应性中的作用 计算机编程…

HTML5实现趣味飞船捡金币小游戏(附源码)

文章目录 1.设计来源1.1 主界面1.2 游戏中界面1.2 飞船边界框效果 2.效果和源码2.1 动态效果2.2 源代码 源码下载 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/143799554 HTML5实现趣味飞船捡金币小游戏(附源码)&…

掌握Golang中的数据竞争检测:runtime/race包全面教程

掌握Golang中的数据竞争检测&#xff1a;runtime/race包全面教程 引言数据竞争问题概述数据竞争的定义数据竞争对程序的影响常见数据竞争场景 Golang runtime/race包概述runtime/race包简介启用数据竞争检测使用 go run使用 go build使用 go test 基本用法与示例单元测试中的使…

Android 关于使用videocompressor库压缩没有声音和异常的问题

原库地址 https://gitcode.com/gh_mirrors/vi/VideoCompressor/overview 这个库用起来比较方便&#xff0c;使用Android原生的MediaCodecmp4parser的方式进行压缩&#xff0c;不用接入so库也不用适配cpu 问题 接口库后你会发现过时了&#xff0c;所以你一阵捣鼓后你发现压缩…

SQL 语句优化及编程方法

DBMS生成的执行计划在很大程度上要受到代码外部结构的影响。因此要想优化查询性能&#xff0c;就必须要知道如何写代码才能使优化器的执行效率更高。 但是&#xff0c;不能为了“效率”牺牲代码的可读性&#xff0c;要让代码清晰。 1 查询优化 在解决SQL造成的性能问题时&am…