문제 – 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]); } }