当前位置： 首页 > article >正文

2313: 砸金蛋

article 2024/11/6 8:02:17

题目描述

Mike获得一个特技，“透视”，即不用打开箱子，就能看到箱子里有什么。于是他去参加砸金蛋的游戏，一根绳子上依序挂着n个金蛋，每个金蛋内有一个纸条，上面写了一个整数作为奖励，游戏参与者可以且仅可以选择绳子上的连续的一串金蛋，比如第二号到第五号。Mike利用特异功能已经先看到了所有金蛋内的纸条上的数值，请你帮他编写一个程序，找到一个起点和终点，使得Mike获得的奖励值最大。

输入描述

输入格式 第一行输入一个正整数； 第二行有n个整数，是每个金蛋内的数字-32768 ≤ a[i] ≤ 32767。

输出描述

输出 第一行有一个整数，表示起始位置编号。 第二行有一个整数，表示终止位置编号。 第三行有一个数，是奖励的和。 注：若有多个解，只输出起始位置编号最小的解，若多个解终止位置编号相同，则输出最小的编号。

输入样例 复制

5
-2 2 5 -1 6

输出样例 复制

2
5
12

提示

对于30%的数据,n<=100
对于60%的数据,n<=400
对于100%的数据,n<=1,000,000

来源 第10章《贪心算法》 

#include<bits/stdc++.h>
using namespace std;
3-struct ice{int ti;int wi;}a[500];7bool cmp(ice x,ice y){return x.wi>y.wi;
bool f[1010];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].ti>>a[i].wi,
sort(a+1,a+n+1,cmp);int ans=0;for(int i=1;i<=n;i++){bool ff=日;for(int j=a[i].ti;j>=1;j--){if(f[j]==0){f[j]=1;ff=1;break;
if(ff==0)ans+=a[i].wi;
cout<<ansreturn 8;


http://www.kler.cn/a/273013.html

相关文章：

  • 基于SpringBoot的植物园管理小程序【附源码】
  • Rust 力扣 - 1652. 拆炸弹
  • 大型音频模型：AudioLLMs
  • 探索Python编程：从入门到实践的全面指南
  • vue3 怎么判断数据列是否包某一列名
  • 什么是信息安全管理体系？
  • 类与对象题目
  • swagger使用手册
  • 【DFS深度优先搜索专题】【蓝桥杯备考训练】：迷宫、奶牛选美、树的重心、大臣的旅费、扫雷【已更新完成】
  • Window部署AgileConfig
  • 传统电力运维企业的数字化转型案例
  • android 简单快速 自定义dialog（简单好用，不需要设置样式）
  • 滑块验证码
  • 算法之前缀和
  • TypeScript中的 K、T 、V
  • MiniGPT-5: 通过生成性视觉标记实现交错式视觉与语言生成
  • 使用wx:for()
  • redis配置文件详情
  • 全基因集GSEA富集分析
  • 基于Andriod的连锁药店管理系统(源码|论文)
  • npm WARN config init.license Use `--init-license` instead.
  • Python爬虫从基础到入门：script标签中的数据
  • Mosquitto MQTT服务器和客户端简单命令
  • 【前缀和】100255. 成为 K 特殊字符串需要删除的最少字符数
  • BUGKU-WEB cookies
  • week07day03(power bi dax公式 零售数据业务分析)