11062번: Card Game

https://www.acmicpc.net/problem/11062

c[i]: i번째 카드에 쓰인 수
dp[i][j]: j-i+1, j-i+2, ..., j번째 카드가 남았을 때 선수 플레이어가 만들 수 있는 최대 합
dp[i][j] = sum(c[k]: j-i<k<=j) - min(dp[i-1][j-1],dp[i-1][j])

시간복잡도는 테스트 케이스마다 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int s[1001], n, t;
int main() {
    for (scanf("%d", &t); t--;) {
        int dp[1001] = {};
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] += s[i - 1];
        for (int i = 1; i <= n; i++) for (int j = n; j >= i; j--) dp[j] = s[j] - s[j - i] - min(dp[j - 1], dp[j]);
        printf("%d\n", dp[n]);
    }
    return 0;
}