石头剪刀布

2017-12-26 19:09:48来源:CSDN作者:Soul_97人点击

分享

7-7 石头剪刀布(15 分)

你可能听说过“石头剪子布”的游戏。牛喜欢玩类似的游戏,他们称之为“蹄子剪子布”。

“蹄子剪子布”的规则很简单,由两头母牛参与。她们都数到三,然后同时作出一个手势,代表一个蹄(Hoof),一张纸(Paper),或一把剪刀(Scissors)。蹄子赢剪刀(因为蹄子可以砸一把剪刀),剪刀赢纸(因为剪刀可以剪纸),还有纸赢蹄(因为蹄子可以剪纸)。例如,如果第一头牛做出“蹄”手势,第二头做出“纸”手势,则第二头牛胜出。当然,如果两头母牛做出相同的姿势,也算作平局。

Farmer John想和他最好的一头牛Bessie进行N局在“蹄,纸,剪刀”的游戏。Bessie作为游戏的专家,可以预测每一个FJ的手势,然后才能做出来。不幸的是,Bessie是个牛,也很懒惰。因此,她倾向于连续多次出相同的手势。事实上,她只愿意在整个游戏中多做一次手势。例如,她可能会为前面的x次游戏出“蹄”,然后换成剩余的N-x次游戏出“纸”。

已知FJ将要进行的手势顺序,请确定Bessie能赢的最大游戏轮数。

输入格式:

输入文件的第一行包含N.

其余的N行包含FJ的手势,每个是H或P或S.

输出格式:

输出Bessie能赢的最大数量的游戏,注意她最多只能改变一次手势。

输入样例:

5PPHPS

输出样例:

4

数据规模:

  • 对于50%的数据,1<=N<=2500
  • 对于100%的数据,1≤N≤100,000
核心就是求前x个位置最多相同的字符加上n-x个这么多位置上相同字符个数,这两部分的和因为整个过程最多变两次,当然也可能不变,定义3个数组分别记录到第i个的时候 从0到i之间又多少个这个字符,有点动态规划的意思,然后从第一个位置枚举每种情况  石头剪刀布一共又6种组合方式  定义maxn  枚举过程中取最大值即可
#include<bits/stdc++.h>using namespace std;int h[100005],p[100005],s[100005];//存石头剪刀布的数组 int main(){	//h 石头 p 布 s 剪刀     int n;    cin>>n;    int sumh,sump,sums; // 数量	sumh = sump = sums = 0; //初始化	int maxn = 0;	char c;	for(int i =0;i <n;i ++)	{		cin>>c;     //读入字符 		if(c == 'P')		{			sump ++;		}		if(c == 'H')		{			sumh ++;		}		if(c == 'S')		{			sums ++;		}		//每个位置存初始位置到当前位置对应字符的个数 		h[i] = sumh;		p[i] = sump;		s[i] = sums;	}	if(maxn < sums)	maxn = sums;	if(maxn < sump)	maxn = sump;	if(maxn < sumh)	maxn = sumh;	//6中组合中找最大值	//hp hs ps ph sh sp	for(int i = 0;i < n;i ++)	{		if(maxn < h[i] + sump - p[i])		maxn = h[i] + sump - p[i];				if(maxn < p[i] + sumh - h[i])		maxn = p[i] + sumh - h[i];				if(maxn < h[i] + sums - s[i])		maxn = h[i] + sums - s[i];				if(maxn < s[i] + sumh - h[i])		maxn = s[i] + sumh - h[i];				if(maxn < p[i] + sums - s[i])		maxn = p[i] + sums - s[i];				if(maxn < s[i] + sump - p[i])		maxn = s[i] + sump - p[i];	} 	cout<<maxn;    return 0;}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台