如何用动态规划求解竞争规划任务？(CodeForces)

Question

条件是：

Ayoub和基拉尼感觉板，而他们要去ArabellaCPC (安曼-埃尔比德)道路，所以基拉尼发明了一个新的游戏与阿尤布。

游戏由以下规则描述：

Ayoub选择一个随机整数n (1≤n≤109)，Kilani选择一个随机整数k (1≤k≤n)，然后他们将开始播放。在每个回合中，玩家可以选择任何数字x (1≤x≤max(1,m−k)) (m是n的当前值)，并从n中减去它。如果n等于zero，那么玩家就不能移动。不能移动的玩家被认为输掉了比赛。

如果基拉尼首发，每个球员发挥最佳，谁会是赢家？

事实上，我是一个淡水的竞争程序，完全不能想出正确的想法。我写了一些东西，但我无法得到这样正确的方式，因为它给了我错误的结果。

#include <iostream>
#include <string>
#include <iterator>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <numeric>
#include <iomanip>
#include <numeric>
#include <deque>
#include <cmath>

int bestWin(int m, int k)
{
    if (m - k <= 0)
        return 0;

    std::vector<int> availableNumbers(m - k);
    std::iota(availableNumbers.begin(), availableNumbers.end(), 1);

    std::vector<int> possibleWins;

    for (auto i = 0; i < availableNumbers.size(); i++)
    {
        possibleWins.push_back(bestWin(m - availableNumbers[i], k));
    }

    return *std::max_element(possibleWins.begin(), possibleWins.end()) + 1;
}

int main()
{
    int testCases;
    std::cin >> testCases;

    while (testCases--)
    {
        int n, k;

        std::string numbers;
        std::cin.get();
        std::getline(std::cin, numbers);
        std::istringstream iNumbers(numbers);
        iNumbers >> n; iNumbers >> k;

        std::cout << bestWin(n, k);
    }

    return 0;
}

你能解释一下我该怎么做吗？我想是动态规划..。我不知道我能在哪里寻求其他地方的帮助.

Answer 1

您不需要动态编程来解决这个问题。请考虑以下几点：

当

• 时，x唯一可以选择的值是1 (x<=max(1，n)
• ，当n > k+1可以为x选择任何值时)，所以基拉尼总是通过选择n-k或n-k-1并达到k或k+1 (下面解释)H 213f<214/code>而获胜的。

对于第一点，你只需要检查一下k是奇数还是偶数，因为基拉尼可以在一次移动中到达k，之后玩家将交替移除1每一轮。在这种情况下，如果k是奇数，Ayoub赢了，Kilani赢了。

对于第二点，根据k的奇偶性，基拉尼可以选择n-k或n-k-1，例如：

n = 10, k = 3
Kilani chooses max(1, m-k) = max(1, 10-3-1) = 6
n = 4
Ayoub chooses max(1, m-k) = max(1, (any number)-3) = 1
n = 3
then they keep alternating picking ones and Kilani will win

因此，您可以修改代码以执行以下操作：

while (testCases--)
{
    int n, k;

    std::string numbers;
    std::cin.get();
    std::getline(std::cin, numbers);
    std::istringstream iNumbers(numbers);
    iNumbers >> n; iNumbers >> k;

    if (n-k == 1 && (k&1)) {
        std::cout << "Ayoub";
    } else {
        std::cout << "Kilani";
    }
}