Untitled
user_1164828
plain_text
a month ago
1.4 kB
1
Indexable
Never
//Game With Numbers #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("Text.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; }
Leave a Comment