BOJ – 카드게임(11062)

문제 – BOJ – 카드게임

2015년 ACM ICPC 인터넷 예선에 출제된 문제이다.

대회에서 푼 것보다 나중에 집에서 다시 풀 때 더 오래걸렸던 것 같다.

d[i][j] = i번째 턴에 j-i+1~j번째 카드 셋에서의 maximum 점수

#include 
#include 

using namespace std;

int d[1010][1010],a[1010],s[1010],n;
int main ()
{
	int T,i,j,k;

	scanf ("%d",&T);
	while (T--)
	{
		scanf ("%d",&n);
		for (i=1;i<=n;i++)
			scanf ("%d",a+i),d[1][i]=a[i],s[i]=s[i-1]+a[i];

		for (i=2;i<=n;i++)
			for (j=1;j<=n-i+1;j++)
			{
				k=i+j-1;
				d[i][k] = max (a[j] + s[k]-s[j] - d[i-1][k], a[k] + s[k-1]-s[j-1] - d[i-1][k-1]);
			}
		printf ("%d\n",d[n][n]);
	}

}