Это постановка проблемы:
Это игра для двух игроков. Изначально в массиве есть n целых чисел, и игроки A и B получают возможность взять их поочередно. Каждый игрок может брать одно или несколько чисел с левого или правого конца массива, но не может брать с обоих концов одновременно. Он может взять столько последовательных чисел, сколько захочет в течение своего времени. Игра заканчивается, когда все числа взяты из массива игроками. Очки каждого игрока подсчитываются путем суммирования чисел, которые он взял. Каждый игрок пытается получить больше очков от другого. Если оба игрока играют оптимально и игрок А начинает игру, то насколько больше очков может получить игрок А, чем игрок Б?
Вход
Вход состоит из нескольких случаев. Каждый случай начинается со строки, определяющей целое число
n (0 < n ≤100)
, количество элементов в массиве. После этого для игры даютсяn
числа. Ввод завершается строкой, гдеn=0
.Выход
Для каждого набора входных данных выведите число, обозначающее максимальную разницу, которую получил первый игрок, оптимально сыграв в эту игру.
Sample Input Output for Sample Input
4
4 -10 -20 7 7
4
1 2 3 4 10
5
4 -10 -20 7 19 12
0
Это решение этой проблемы.
#include<stdio.h>
#include<stdlib.h>
#define maxn 103
//typedef long long bg;
typedef long bg;
bg Table[maxn][maxn];
bg Seq[maxn];
bool Flag[maxn][maxn];
bg N;
bg Sum(int l, int r) {
int i, sum = 0;
for (i = l; i <= r; i++)
sum += Seq[i];
return sum;
}
bg Recur(int L, int R) {
bg max, i, d, k;
if (L == R)
return Seq[L];
if (Flag[L][R])
return Table[L][R];
max = Sum(L, R);
d = Seq[L];
for (i = L + 1; i <= R; i++) {
k = Recur(i, R);
if ((d - k) > max)
max = d - k;
d += Seq[i];
}
d = Seq[R];
for (i = R - 1; i >= L; i--) {
k = Recur(L, i);
if ((d - k) > max)
max = d - k;
d += Seq[i];
}
Flag[L][R] = true;
Table[L][R] = max;
return max;
}
void Cal() {
bg max, i, d, k;
max = Sum(1, N);
d = Seq[1];
for (i = 2; i <= N; i++) {
k = Recur(i, N);
if ((d - k) > max)
max = d - k;
d += Seq[i];
}
d = Seq[N];
for (i = N - 1; i >= 1; i--) {
k = Recur(1, i);
if ((d - k) > max)
max = d - k;
d += Seq[i];
}
printf("%ld\n", max);
}
void Reset() {
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++)
Flag[i][j] = false;
}
}
int main() {
//freopen("in.txt", "r", stdin);
int i;
while (scanf("%ld", &N) && N) {
for (i = 1; i <= N; i++)
scanf("%ld", &Seq[i]);
Cal();
Reset();
}
return 0;
}
Я отлаживал его, но мне было трудно понять решение.
Может ли кто-нибудь объяснить код или решение этой проблемы. Или кто-нибудь может опубликовать код для решения этой проблемы с помощью динамического программирования, а не рекурсии?