题解 | #石头剪刀布#

题号：NC14400

链接：https://ac.nowcoder.com/acm/problem/14400

来源：牛客网

题目描述

齐齐和司机正在玩剪刀石头布，不过他俩有些玩腻了，所以思考了一个全新的“剪刀石头布”的游戏。

全新的“剪刀石头布“”的胜负规则和剪刀石头布一样，每人有3种手势，分别为剪刀（scissors）、石头（rock）、布（paper）。剪刀胜于布，布胜于石头，石头胜于剪刀，当手势相同时为平局。

齐齐可以在司机出手势后再出自己的手势，但是不能连续两局出同一种手势。

他们一共进行n盘对局。每一盘中，胜者+1分，败者-1分，平局两人都不扣分。

已知司机的n局的出手势情况，求齐齐进行n盘对局后获得的最高分数。

思路：

典型的dp问题（动态规划）

变量参数有两个：1.进行到第i轮，2.上一轮出的是什么。

dp[i][k]：代表第i轮比赛时候出k的最高分数。

说明:0代表石头,1代表布，2代表剪刀

那么dp[i][0]=max(dp[i-1][1]+dp[i-1][2])+当前第i轮出石头的分数

dp[i][1]=max(dp[i-1][0]+dp[i-1][2])+当前第i轮出布的分数

dp[i][2]=max(dp[i-1][0]+dp[i-1][1])+当前第i轮出剪刀的分数

最后一轮，必然出三个中一个，最大分数为max(dp[i][0],dp[i][1],dp[i][2])

注:附代码开的数组为dp[2][3],而不是dp[n][3],是采用滚动数组优化空间

附代码:

// dddd.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <vector>
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;
// 0:rock
// 1:paper
// 2:scissors
int getPoint(char opponent, char me) {
	if (opponent == me) return 0;

	if(opponent == 'r' && me == 'p')return 1;
	if (opponent == 'p' && me == 's')return 1;
	if (opponent == 's' && me == 'r')return 1;

	return -1;
}
int main() {
	int n;
	cin >> n;
	char s[111];
	int dp[2][3] = {};
	cin >> s;
	dp[0][0] = getPoint(*s, 'r');
	dp[0][1] = getPoint(*s, 'p');
	dp[0][2] = getPoint(*s, 's');
	for (int i = 1; i < n; i++) {
		cin >> s;
		dp[i & 1][0] = MAX(dp[(i - 1) & 1][1], dp[(i - 1) & 1][2]) + getPoint(*s, 'r');
		dp[i & 1][1] = MAX(dp[(i - 1) & 1][0], dp[(i - 1) & 1][2]) + getPoint(*s, 'p');
		dp[i & 1][2] = MAX(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1]) + getPoint(*s, 's');
	}
	cout << MAX(MAX(dp[(n - 1) & 1][0], dp[(n - 1) & 1][1]), dp[(n - 1) & 1][2]) << endl;
}