c - 如何用动态规划解决竞争性编程任务？（代码部队）

问题描述

条件是：

Ayoub 和 Kilani 在前往 (Amman-Irbid) 路的 ArabellaCPC 时感觉到了板子，所以 Kilani 发明了一个新游戏来和 Ayoub 一起玩。

游戏由以下规则描述：

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;
}

你能解释一下我应该使用什么方法吗？我想这是动态编程...我不知道在哪里可以向其他地方寻求帮助...

标签： cdynamic-programming

解决方案

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

当n <= k+1那么唯一可以选择的值x是1(x<=max(1, nk)
当n > k+1您可以选择任何值时，xKilani 将始终通过选择n-k或n-k-1达到k或获胜k+1（如下所述）

对于第一点，您只需要检查k是奇数还是偶数，因为 Kilani 可以k一次到达，然后玩家将交替移除1每一轮。在这种情况下，如果k是奇数，则 Ayoub 获胜，否则 Kilani 获胜。

对于第二点，根据kKilani 的奇偶性可以选择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";
    }
}

c - 如何用动态规划解决竞争性编程任务？（代码部队）

问题描述

解决方案

推荐阅读