牛客 第二十届西南科技大学ACM程序设计竞赛(同步赛):祖玛

本文主要是介绍牛客 第二十届西南科技大学ACM程序设计竞赛(同步赛):祖玛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


 

题目描述

wzy 在玩一种很新的祖玛。

给定一个仅包含 小写字母 的字符串 sss , sss 由 mmm 个不同的小写字母组成,每个字母代表一种小球,在消去时会获得 相应 的分数:


  • 两个及以上 相同的小球相碰就会消失(在发射小球前因为无相碰,所以有两个及以上小球相邻也不会消失)。
  • 每次碰撞后,消失获得的分数为:对应小球分数×消失个数

     

你可以进行 一次 操作:

发射一个任意小球于 sss 的任意位置(也可以是 头和尾 )。

发射小球后,按照规则进行,直到不能碰撞为止。

请你求出经过一次操作后取得的 最大分数

输入描述:

 

第一行包含两个整数 n,m(1≤n≤105,1≤m≤26)n,m(1\le n \le 10^5,1\le m\le 26)n,m(1≤n≤105,1≤m≤26) - 表示字符串长度 和 字符集大小。

第二行包含一个长度为 nnn 字符串 sss。

接下来 mmm 行,每行包含 c,k(′a′≤c≤c,k('a'\le c\lec,k(′a′≤c≤ ′z′,1≤k≤109)'z',1\le k\le10^9)′z′,1≤k≤109) - 表示每消除一个字母 ccc 有 kkk 分。

保证:字符串 sss 中的字母必定在给定字符集中出现。

输出描述:

输出一次操作能获得的最高得分。

示例1

输入

复制6 3 abccba a 1 b 2 c 3

6 3
abccba
a 1
b 2
c 3

输出

复制15

15

说明

样例一的解释:

最终将全部字母消除,得分为 3×3+2×2+2×1=153×3+2×2+2×1 = 153×3+2×2+2×1=15 即为最大
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s,s2;
long long score[30];
long long ans;
int p[300010];
long long pre[100010];
void mlc(){int mid,mr=0;for(int i=1;i<s2.size();i++){if(i<mr) p[i]=min(p[mid*2-i],mr-i);else p[i]=1;while(s2[i-p[i]]==s2[i+p[i]]) p[i]++;if(i+p[i]>mr){mr=i+p[i];mid=i;}}
}
int main(){scanf("%d%d",&n,&m);cin>>s;for(int i=1;i<=m;i++){char c;long long num;cin>>c;scanf("%lld",&num);score[c-'a']=num;}s2+='&';s2+=s[0];pre[1]=score[s2[1]-'a'];for(int i=1,j=1;i<s.size();i++){if(s[i]!=s[i-1]) {s2+=s[i];j++;pre[j]=pre[j-1]+score[s[i]-'a'];//s2的前缀和}else{pre[j]+=score[s[i]-'a'];}}s2+='^';
//将s中连续出现的某个字母合并成只有一个,最终形成s2,这样的s2的回文串只能为奇数,因此直接头和尾加一个不同的字符即可,不用再加‘#’mlc();for(int i=1;i<s2.size();i++){long long res;res=pre[i+p[i]-1]-pre[i-p[i]]+score[s2[i]-'a']; //以i为中心,左右分别延长p[i]-1的回文串ans=max(ans,res);}cout<<ans;
}

这篇关于牛客 第二十届西南科技大学ACM程序设计竞赛(同步赛):祖玛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1068412

相关文章

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Linux搭建Mysql主从同步的教程

《Linux搭建Mysql主从同步的教程》:本文主要介绍Linux搭建Mysql主从同步的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux搭建mysql主从同步1.启动mysql服务2.修改Mysql主库配置文件/etc/my.cnf3.重启主库my

Java中将异步调用转为同步的五种实现方法

《Java中将异步调用转为同步的五种实现方法》本文介绍了将异步调用转为同步阻塞模式的五种方法:wait/notify、ReentrantLock+Condition、Future、CountDownL... 目录异步与同步的核心区别方法一:使用wait/notify + synchronized代码示例关键

详谈redis跟数据库的数据同步问题

《详谈redis跟数据库的数据同步问题》文章讨论了在Redis和数据库数据一致性问题上的解决方案,主要比较了先更新Redis缓存再更新数据库和先更新数据库再更新Redis缓存两种方案,文章指出,删除R... 目录一、Redis 数据库数据一致性的解决方案1.1、更新Redis缓存、删除Redis缓存的区别二

Nacos集群数据同步方式

《Nacos集群数据同步方式》文章主要介绍了Nacos集群中服务注册信息的同步机制,涉及到负责节点和非负责节点之间的数据同步过程,以及DistroProtocol协议在同步中的应用... 目录引言负责节点(发起同步)DistroProtocolDistroSyncChangeTask获取同步数据getDis

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展

【科技明说 | 科技热点关注】 2024戴尔科技峰会在8月如期举行,虽然因事未能抵达现场参加,我只是观看了网上在线直播,也未能采访到DTF现场重要与会者,但是通过数十年对戴尔的跟踪与观察,我觉得2024戴尔科技峰会给业界传递了6大重要信号。不妨简单聊聊:从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展? 1)退出中国的谣言不攻自破。 之前有不良媒体宣扬戴尔将退出中国的谣言,随着2