首页 > 代码库 > 【推导】【贪心】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem D. Clones and Treasures
【推导】【贪心】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem D. Clones and Treasures
给你一行房间，有的是隐身药水，有的是守卫，有的是金币。
你可以任选起点，向右走，每经过一个药水或金币就拿走，每经过一个守卫必须消耗1个药水，问你最多得几个金币。
药水看成左括号，守卫看成右括号，
就从每个位置贪心地向右走，如果在 r 遇到不匹配，则把下一次的左端点置成r+1，接着走。
O（n）即可。
因为如果把左端点放在上次的l和r之间，要么会发生不匹配，要么答案无法比上次走的更优。
队友代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <cstring>
#include <vector>
#include <ctime>
using namespace std;
char s[1100000];
int now,all,i,l,ans;
int main()
{
// freopen("ac.in","r",stdin);
// freopen("ac.out","w",stdout);
gets(s); l=strlen(s);
for (i=0;i<l;i++)
{
if (s[i]==‘K‘)
{
all--;
if (all<0)
{
now=0;
all=0;
continue;
}
}
if (s[i]==‘M‘)
{
now++;
ans=max(ans,now);
}
if (s[i]==‘H‘) all++;
}
printf("%d\n",ans);
}
【推导】【贪心】XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem D. Clones and Treasures
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。