Решение задачи "Игра с монетами" с Меньшиков

Без пояснения   Просмотров: 16


Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
#define USE_VECTOR
 
#ifdef USE_VECTOR
vector<vector<int> > keep; // keep[k][n] - сколько монет получишь если K = k и осталось n стопок
vector<vector<int> >leave; // leave[k][n] - сколько монет оставишь, если сделаешь ход keep[k][n]
#else
int keep[85][185], leave[85][185];
#endif
 
int n,k;
vector<int> mas,sums;
 
void input()
{
    cin>>n;
    mas.resize(n);
    sums.resize(n);
    for (int i=0;i<n;i++)
    {
        cin>>mas[i];
        sums[i] = mas[i];
        if (i!=0)
            sums[i] += sums[i-1];
           
    }
    cin>>k;
 
#ifdef USE_VECTOR
    keep = vector<vector<int> >(k, vector<int>(n+1,0));
    leave = vector<vector<int> >(k, vector<int>(n+1,0));
#endif
}
 
// быстрый подсчет суммы элементов в интервале [f,s]
inline int sum(int f, int s)
{
    return sums[s] - sums[f] + mas[f];
}
void solve()
{
    // заполняем первую строчку в обоих матрицах
    // используя принцип чередования ходов
    keep[0][n-1] = mas[n-1];
    for (int j = n-2; j>=0;j--)
    {
        keep[0][j]  = keep[0][j+2] + mas[j];
        leave[0][j] = keep[0][j+1];
    }
 
    for (int i = 1; i < k; i++)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            // находим наилучший ход сверху,
            // т.е находим наилучший ход, если будем уменьшать K
            int MaxUpKeep = 0;
            int posUp = 0;
            for (int p = i - 1; p >= 0; p--)
            {
                if (MaxUpKeep < keep[p][j])
                {
                    MaxUpKeep = keep[p][j];
                    posUp = p;
                }
            }
            // находим наилучший ход справа,
            // т.е. оставляем K без изменений
            int last = min(j + i, n-1);
            int MaxRightKeep = sum(j,last) + leave[i][last+1];
 
            if (MaxUpKeep > MaxRightKeep)
            {
                keep[i][j]  = keep[posUp][j];
                leave[i][j] = leave[posUp][j] ;
            }
            else
            {
                keep[i][j]  = MaxRightKeep;
                leave[i][j] = keep[i][last+1];
            }
        }
    }
}
void output()
{
    cout<<keep[k-1][0];
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    output();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться