# Untitled

unknown
plain_text
7 months ago
1.4 kB
1
Indexable
Never
```#include <iostream>

#define SIZE 30
using namespace std;

int data[SIZE], MAX[SIZE][SIZE],MIN[SIZE][SIZE];

#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)

int Easy(int i, int j) {
if (i > j) {
return 0;
}

if (MAX[i][j])
return MAX[i][j];

int t1 = data[i] + Easy(i + 1, j - 1);
int t2 = data[i] + Easy(i + 2, j);

int t3 = data[j] + Easy(i + 1, j - 1);
int t4 = data[j] + Easy(i, j - 2);

return MAX[i][j] = Max(Max(t1, t2), Max(t3, t4));
}

int Hard(int i,int j) {
if (i > j) {
return 0;
}

if (MIN[i][j])
return MIN[i][j];

int t1 = data[i] + Hard(i + 1, j - 1);
int t2 = data[i] + Hard(i + 2, j);

int t3 = data[j] + Hard(i + 1, j - 1);
int t4 = data[j] + Hard(i, j - 2);

return MIN[i][j] = Max(Min(t1, t2), Min(t3, t4));
}

int main() {
int T, K;

freopen("input.txt", "r", stdin);

cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> K;
for (int i = 0; i <K; i++) {
cin >> data[i];
}

for (int i = 0;i <SIZE; i++) {
for (int j = 0;j <SIZE; j++) {
MAX[i][j]=0;
MIN[i][j]=0;
}
}

int Ea = Easy(0, K-1);
int Ha = Hard(0, K-1);

cout << "Case #" << tc << endl << Ea << " " << Ha << endl;
}
return 0;
}```