首页 > 试题广场 >

队列得分

[编程题]队列得分
  • 热度指数：2192 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解

小M和大M要通过选择元素组成队列进行得分pk。目前存在队列S1,S2,S3...Sn,每个元素包括2个正整数属性set和value.从中选出任意K个元素S[i1],S[i2]...S[ik],保证顺序不变即i1 < i2 < i3< ... < ik,组成新的队列P1,P2,P3......Pk.我们通过一个机制评价队列的好坏:

Base=P1.value+P2.value+...Pk.value,

Bonus=10*t;t为新队列中Pi.set=P(i+1).set的i个数.

最终得分Score=Base-Bonus;求Score的最大值和取最大值时新队列元素个数的最小值.


输入描述:
第一行包含一个数N(0 < N <= 500)

接下来N行每一行两个数表示S1,S2,...,Sn的set和value值  (0 < set,value <= 20)


输出描述:
Score的最大值和新队列元素个数的最小值
示例1

输入

5
1 10
1 5
2 4
3 9
4 8

输出

31 4

说明

选S1,S3,S4,S5
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 18:58:57
题解： 考察点： 动态规划，分类讨论 易错点： 题目中指出，而又是取自队列的，因此假设当前位于队列当中的位置，则之前的任何位置都可能成为其在中的上一个位置 解法一：动态规划 设表示在队列中位置的最大值，表示元素个数的最小值。根据在易错点中的分析之前的任意一个位置都可能成为新队列中位置的上一个位置，因 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 贪吃的迪恩顶呱呱
发表于 2024-05-05 11:22:48
#include <iostream> #include <utility> #include <vector> using namespace std; int main() { int n; while (cin >> n) { 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 动态规划 Momenta 模拟 队列 2019 数学 Java工程师
来自：Momenta2019...
上传者：小小
难度：
11条回答 6258浏览

热门推荐

通过挑战的用户

查看代码

相关试题

队列得分

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号