Untitled

mail@pastecode.io avatar
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;
}