백준(BOJ) 11062 카드게임 ***

상당히 까다로운 DP문제입니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 1005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

int t,n,arr[MAX],dp[2][MAX][MAX];

int fun(int st,int fi,bool turn)
{
    if(st==fi)
    {    if(turn)
            return arr[st];
         else
            return 0;
    }
    int &ret = turn ?dp[0][st][fi]:dp[1][st][fi];
    if (ret != -1)
        return ret;
    if (turn)
        ret = max(fun(st + 1, fi,false) + arr[st], fun(st, fi - 1,false) + arr[fi]);
    else
        ret = min(fun(st + 1, fi,true), fun(st, fi - 1,true));
    return ret;
}

int main()
{
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d",&n);
        memset(dp,-1,sizeof(dp));
        for(int k=1;k<=n;k++)
            scanf("%d",&arr[k]);
        printf("%d\n",fun(1,n,true));
    }
    
}