TIOJ 1029 A遊戲

[DP]
還滿有趣的ㄎㄎ

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int line[1001];
int sum[1001];
int dp[1001][1001];
int dfs(int,int);
int dfs(int s,int e)
{
 if(s==e) return line[s];
 if(dp[s][e]) return dp[s][e];
 if(((sum[e]-sum[s])-dfs(s+1,e)+line[s])>((sum[e-1]-sum[s-1])-dfs(s,e-1)+line[e]))
  dp[s][e]=((sum[e]-sum[s])-dfs(s+1,e)+line[s]);
 else
  dp[s][e]=(sum[e-1]-sum[s-1])-dfs(s,e-1)+line[e];
 return dp[s][e];
}
int main()
{
 int n;scanf("%d",&n);
 for(int ln=1;ln<=n;ln++)
  scanf("%d",&line[ln]);
 for(int ln=1;ln<=n;ln++)
  dp[ln][ln]=line[ln];
 sum[0]=0;
 for(int lx=1;lx<=n;lx++)
  sum[lx]=sum[lx-1]+line[lx];
 memset(dp,0,sizeof(dp));
 printf("%d %d\n",dfs(1,n),sum[n]-dfs(1,n));
 return 0;
}