(纪中)2250. NOIP

news/2024/2/29 4:04:35

(File IO): input:noip.in output:noip.out
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
Goto ProblemSet


题目描述
你知道 N e w O r a n g e I n d u s t r y P a l a t a b l e New Orange Industry Palatable NewOrangeIndustryPalatable公司吗?这是老板 S m a r t Smart Smart为了与苹果公司竞争而新开的一家橘子公司,它的业务是栽培美味的橘子并售卖,公司简称为 N O I P NOIP NOIP N O I P NOIP NOIP公司新推出 N + 1 N+1 N+1个橘子,每个橘子上都贴有一个标签,其中有N个普通的橘子上面印有一个 " N " "N" "N" " O " "O" "O" " I " "I" "I"字母。还有一个独一无二的幸运橘子标签印有 " P " "P" "P"字母。 N O I P NOIP NOIP公司搞了一个优惠活动,把N个普通橘子排成一排,从左到右依次编号为 1 ~ N 1~N 1N。让顾客从左到右选三个橘子,如果依次排列组成了 " N O I " "NOI" "NOI",就可获得优惠券。 S m a r t Smart Smart想把贴有标签P的幸运橘插入到排列中的(可以插入到队列的任意位置)。在换取优惠券时, P P P橘子可以作为 N N N橘子或 O O O橘子或I橘子使用。 S m a r t Smart Smart想知道加入 P P P橘子以后,第一个选购的顾客最多有多少种选法可以得到优惠券。


输入
第一行是一个整数 N N N,表示 N O I P NOIP NOIP公司有 N N N个普通橘子。
第二行是一个长度为 N N N的字符串S,仅由 N , O , I N,O,I NOI三个大写英文字母组成。字符串的左数第 i i i个字母表示第 i i i个橘子的标签类型。

输出
输出为一行,表示选择方式的最大值。


样例输入
样例输入1
5
NOIOI

样例输入2
7
NNNOIII

样例输出
样例输出1
6

样例输出2
18


数据范围限制
30 30 30%的数据: 3 ≤ N ≤ 20 3≤N≤20 3N20
60 60 60%的数据: 3 ≤ N ≤ 200 3≤N≤200 3N200
80 80 80%的数据: 3 ≤ N ≤ 3000 3≤N≤3000 3N3000
100 100 100%的数据: 3 ≤ N ≤ 100000 3≤N≤100000 3N100000


提示
样例 1 1 1中将 " P " "P" "P"放在 " N O I O I " "NOIOI" "NOIOI" " N " "N" "N"前一个位置或后一个位置,并将 " P " "P" "P"作为 N N N橘子使用,最多有6种选法可以得到优惠券。
样例 2 2 2中将"P"放在 " N N N O I I I " " NNNOIII " "NNNOIII" " O " "O" "O"前一个位置或后一个位置,并将 " P " "P" "P"作为 O O O橘子使用,最多有 18 18 18种选法可以得到优惠券。


解题思路
一系模拟+一系列优化,具体看看代码里的解释吧。。。


代码

#include<bits/stdc++.h>
using namespace std;
string s;
long long  n,sn,si,an,ai,ao,ans,a[100005],b[100005];
int main(){freopen("noip.in","r",stdin);freopen("noip.out","w",stdout);scanf("%d",&n);cin>>s;for(int i=0;i<n;i++)if(s[i]=='I')si++;//先统计I的个数for(int i=0;i<n;i++){if(s[i]=='N')sn++;//前面N的个数(包括本身)a[i]=sn;if(s[i]=='I')si--;//后面I的个数(包括本身)b[i]=si;if(s[i]=='O')ans+=a[i]*b[i],an+=sn,ai+=si;//计算插入O会增加几个方案数~}for (int i=0;i<n;i++)ao=max(ao,a[i]*b[i]);//然后一系列比较ans+=max(ao,max(an,ai));//接着还是一系列比较printf("%lld",ans);
}

http://www.ppmy.cn/news/142563.html

相关文章

【LeetCode】2250. Count Number of Rectangles Containing Each Point

基本上就是Binary Search 简单二分 因为题目的height只有100种可能&#xff0c;我的naive的想法是统计每个height的width&#xff0c;然后遍历到每个点(x, y)的时候&#xff0c;把height>y的每个width数组都二分查找一遍…… from collections import defaultdict from b…

洛谷P3258BZOJ3631DTOJ2250 [JLOI2014]松鼠的新家

洛谷P3258&&BZOJ3631&&DTOJ2250 [JLOI2014]松鼠的新家 题目题目描述输入格式输出格式样例样例输入样例输出 数据范围与提示 题解 题目 题目描述 松鼠的新家是一棵树&#xff0c;前几天刚刚装修了新家&#xff0c;新家有 n n n个房间&#xff0c;并且有 n − …

系统开发视角下的诊断 ———— 动力系统(P)诊断故障8

文章目录 P22XX 燃油和空气计量和辅助排放控制P23XX 点火系统或失火 P22XX 燃油和空气计量和辅助排放控制 P22XX Fuel and air metering and auxiliary emission controls DTC Number DTC Name Location P2200 NOx Sensor Circuit Bank 1 P2201 NOx Sensor Circuit Range/Perf…

NOIP——jzoj 2250

题目描述 你知道New Orange Industry Palatable公司吗&#xff1f;这是老板Smart为了与苹果公司竞争而新开的一家橘子公司&#xff0c;它的业务是栽培美味的橘子并售卖&#xff0c;公司简称为NOIP。 NOIP公司新推出N1个橘子&#xff0c;每个橘子上都贴有一个标签&#xff0c;其…

poj 2250

题目实际意思&#xff0c;就是找两篇文章中的“最多公共单词”——其实可以把它转换成最长公共子序列问题&#xff0c;只是这里的序列的元素不是字母而是单词罢了。 另外&#xff0c;此题主要是考察LCS的形成路径&#xff0c;因此需要一个数组记录这个路径&#xff0c;这里用的…

poj - 2250 题解

题意&#xff1a;魔改版的LCS问题。序列是单词序列 解法&#xff1a;原版LCS的序列元素是数字&#xff0c;想办法把数字替换成单词就解决了 1 #include<iostream>2 #include<cstdio>3 #include<algorithm>4 #include<cstring>5 #include<string>…

loj2250/bzoj4784/洛谷P3687 仙人掌 DP

题目分析 如果原图不是一个仙人掌&#xff0c;答案就是0. 对于一个环&#xff0c;环上的两个点&#xff0c;若分别连着不是该环上的点&#xff0c;点集为 S 1 S_1 S1​和 S 2 S_2 S2​&#xff0c;那么 S 1 S_1 S1​和 S 2 S_2 S2​之间不能连边。所以我们可以去掉所有环上的…

2250. NOIP

2250. NOIP 题目描述 你知道New Orange Industry Palatable公司吗&#xff1f;这是老板Smart为了与苹果公司竞争而新开的一家橘子公司&#xff0c;它的业务是栽培美味的橘子并售卖&#xff0c;公司简称为NOIP。 NOIP公司新推出N1个橘子&#xff0c;每个橘子上都贴有一个标签&a…

Compromise (p2250)

第二次做&#xff0c;不过一开始没有看清会是多组数据&#xff0c;都搞得我都不知道哪错了。 这个和找公共子序列是一个道理&#xff08;把一个单词看成是一个字母&#xff09;。输出的路径进行记录&#xff0c;pre[][]&#xff0c;其中3代表是左上&#xff0c;2代表左边&…

巧用HashSet装载非重数据(洛谷P2250题题解,Java语言描述)

题目要求 P2550题目链接 分析 其实既然是Java来写&#xff0c;不用集合框架就是浪费啊&#xff01;&#xff01; 比较简单的思路是把中奖号码放进HashSet里&#xff0c;利用Hash来查找。 contains()就避免了又双叒叕疯狂遍历~~ 用一个数组记录中奖情况即可~~ AC代码&#xf…

【802.3】PCS 物理编码子层

Clause82:Physical Coding Sublayer (PCS) for 64B/66B, type 40GBASE-R and 100GBASE-R 文章目录 1. PCS 介绍1.1 概述1.2 功能框图2. PCS 详述2.1 发送方向2.1.1 64B/66B 编码2.1.2 Scrambler 加扰2.1.3 Block distribution 块分发2.1.4 Alignment marker insertion 插入对齐…

踩坑必看!事务隔离级别选择指南,避免数据库操作的陷阱!

大家好&#xff0c;我是你们的小米&#xff0c;在这个阳光明媚的日子里给大家带来一篇关于数据库事务隔离级别的分享。作为数据库领域的重要概念&#xff0c;事务隔离级别对于保障数据的一致性和稳定性至关重要。废话不多说&#xff0c;让我们一起深入了解吧&#xff01; 四个核…

浅谈RPC,gRPC和RESTful

RPC 远程过程调用&#xff08;Remote Procedure Call&#xff0c;RPC&#xff09;是一个计算机通信协议。该协议允许运行于一台计算机的程序调用另一个地址空间&#xff08;通常为一个开放网络的一台计算机&#xff09;的子程序&#xff0c;而程序员就像调用本地程序一样&…

win10删除系统更新的安装包(清除C盘无用资源)

删除 C:\Windows\SoftwareDistribution\Download 下的全部文件&#xff0c;其为安装系统的安装包&#xff0c;一般没啥用&#xff0c;删了后大概可以省下500M空间。

Windows10无法删除更新缓存,删除C盘SoftwareDistribution下Download文件夹内容

windows更新后&#xff0c;C:\Windows\SoftwareDistribution\Download占据几个G空间&#xff0c;并且无法被清理掉。解决办法&#xff1a; 亲测可用&#xff1a; 参考链接&#xff1a;&#xff08;官方回复&#xff09; win10 C盘磁盘清理&#xff0c;清理系统文件无法删除wi…

Softwaredistribution与系统瘦身

本回答来源于“江乡才子”的百度问答&#xff1a; (VS2010 安装失败&#xff0c;想试试更改Softwaredistribution文件夹名再重装&#xff0c;发现根本就更改不了&#xff0c;所以就想知道这到底是个什么东东&#xff0c;这个答案很不错) 其实这只是windows的一个目录&#xf…

C:\windows\softwaredistribution 文件过大如何处理

最近系统盘空闲空间越来越小&#xff0c;经过排查发现这个目录高达3G&#xff0c;网上百度后发现这是Windows升级留下的&#xff0c;不能随便删除。 google一下Windows官方的论坛&#xff0c;现记录下解决办法。 http://answers.microsoft.com/en-us/windows/forum/windows_xp…

SpringBoot接收请求参数的方式

【方式一】原始方式 因为SpringBoot封装了Servlet&#xff0c;所以也允许使用HttpServletRequest类中的方法来获取 /*** 【方式一】原始方式*/RequestMapping("/demo01")public String demo01(HttpServletRequest request) {// 参数名要与页面提交的参数名一致Strin…

Web应用技术(第十四周/END)

本次练习基于how2j和课本,初步认识Spring。 以后我每周只写一篇Web的博客&#xff0c;所有的作业内容会在这篇博客中持续更新。。。 一、Spring基础1.Spring概述:2.Sring组成&#xff1a;3.BeanFactory&#xff1a;4.控制反转&#xff1a;5.依赖注入&#xff1a;6.JavaBean与S…

运营策略:影响内容病毒式传播的 8 个维度

目录 01 第一个影响要素就是内容的类型 02 第二个要素时内容的长度 03 第三个要素是要唤起正确的情感 04 第四个是利用趋势&#xff0c;也就是热点问题或事件 05 第五个是视觉效果 06 第六个是增加作者署 07 第七个是在正确的时间发布内容 08 第八个是影响者的力量 病毒…
最新文章