「SP122」STEVE - Voracious Steve 解题报告

SP122 STEVE - Voracious Steve

题意翻译

Problem

Steve和他的一个朋友在玩游戏,游戏开始前，盒子里有 n个甜甜圈，两个人轮流从盒子里抓甜甜圈，每次至少抓 1个，最多抓m个。

最后一次将当盒子的甜甜圈抓完的人是这一轮游戏胜利者，他可以将所有抓到的甜甜圈吃完，另外一个人是这轮的失败者，他抓到的所有甜甜圈要重新放到盒子里。

下一轮游戏由上一轮的失败者开始抓，游戏继续。直到若干轮后，所有的甜甜圈被吃完，游戏结束。

游戏的目标是吃到尽量多的甜甜圈。游戏最开始，由Steve先抓，两个人均采用最优策略，请问Steve最多可以吃到多少甜甜圈。

Input Data

第一行输入t,表示有t组测试数据

第2~t行，两个整数n和m(1≤m≤n≤100)

Output Data

一行，一个整数，表示Steve最多可以吃到多少个甜甜圈。

题目描述

Steve and Digit bought a box containing a number of donuts. In order to divide them between themselves they play a special game that they created. The players alternately take a certain, positive number of donuts from the box, but no more than some fixed integer. Each player's donuts are gathered on the player's side. The player that empties the box eats his donuts while the other one puts his donuts back into the box and the game continues with the "loser" player starting. The game goes on until all the donuts are eaten. The goal of the game is to eat the most donuts. How many donuts can Steve, who starts the game, count on, assuming the best strategy for both players?

Task

Write a program that:

reads the parameters of the game from the standard input,
computes the number of donuts Steve can count on,
writes the result to the standard output.

输入输出格式

输入格式：

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the first and only line of the input contains exactly two integers n and m separated by a single space, 1 <= m <= n <= 100 - the parameters of the game, where n is the number of donuts in the box at the beginning of the game and m is the upper limit on the number of donuts to be taken by one player in one move.

输出格式：

For each test case the output contains exactly one integer equal to the number of donuts Steve can count on.

输入输出样例

输入样例#1：

1
5 2

输出样例#1：

思路

\(a[all][one][tho]\)表示总共有\(all\)个甜甜圈，现在轮到的人已经取了\(one\)个甜甜圈，另一个人取了\(tho\)个甜甜圈，现在轮到的人最多能取到的甜甜圈数。

我们用记搜方式实现。

当\(all=0\)时，直接返回0。

当\(all\not=0\)时，我们枚举取的个数，从中选出最大值。

一些边界、细节请看代码。

代码

#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[205][205][205];

int SG( int all, int one, int tho ){
    if ( all == 0 ) return 0;
    if ( a[all][one][tho] ) return a[all][one][tho];
    int ans(0);//ans为找出的最大值
    for ( int i = 1; i <= min( m, all - one - tho ); ++i ){
        if ( one + tho + i == all ) ans = max( ans, all - SG( tho, 0, 0 ) );//取完了，把没取到最后一个的人的甜甜圈拿来继续取
        else ans = max( ans, all - SG( all, tho, one + i ) );//没取玩，继续取
    }
    return a[all][one][tho] = ans;//记录答案
}

int main(){
    int T;
    scanf( "%d", &T );
    while( T-- ){
        memset( a, 0, sizeof a );//每次的m都不同，所以别忘了初始化
        scanf( "%d%d", &n, &m );
        printf( "%d\n", SG( n, 0, 0 ) );
    }
    return 0;
}