Это постановка задачи:
Это игра для двух игроков. Первоначально в массиве есть n целых чисел, и игроки A и B получают возможность взять их альтернативно. Каждый игрок может взять одно или несколько чисел с левого или правого конца массива, но не может взять с обоих концов одновременно. Он может взять столько последовательных чисел, сколько захочет в течение своего времени. Игра заканчивается, когда все числа взяты из массива игроками. Очко каждого игрока рассчитывается суммированием взятых им чисел. Каждый игрок пытается набрать больше очков от других. Если оба игрока играют оптимально, и игрок A начинает игру, то сколько очков игрок A может получить больше, чем игрок B?
Input
Вход состоит из нескольких случаев. Каждый случай начинается со строки, указывающей целое число 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;
}
Я сделал отладку, но мне было трудно понять решение.
Может кто-нибудь объяснить код или решение этой проблемы. Или кто-нибудь может опубликовать код для решения этой проблемы с динамическим программированием, а не рекурсией?