Game theory (Optimal game strategy)

                                                   http://www.spoj.com/problems/TWENDS/

TWENDS - Two Ends

 In this problem 1st player  plays  optimally and second player plays greedly.
 We have to pick either from first end or second end.


#include<bits/stdc++.h>

using namespace std;

long long int  dp[2002][2002];
long long int  a[50000];


long long int send(long long int  a[],long long int  st ,long long int  end)
{
  if(st>end)
   return 0;

    if(dp[st][end]!=-1)
    {
       // dp[st][end]=a[st];
        return dp[st][end];
    }

   if(st==end)
   {
     dp[st][end]=a[st];
     return a[st];
   }

   if(st+1==end)
   {
       dp[st][end]=max(a[st],a[end]);
       return max(a[st],a[end]);
   }

else{
    long long int ans1=a[st];
    if(a[st+1]>=a[end])
    {
        ans1+=send(a,st+2,end);
    }
    else
    {
        ans1+=send(a,st+1,end-1);
    }

    long long int  ans2=a[end];
    if(a[st]>=a[end-1])
    {
        ans2+=send(a,st+1,end-1);
    }
    else
    {
        ans2+=send(a,st,end-2);
    }

   dp[st][end]=max(ans1,ans2);
}


   return dp[st][end];
}







int main()
{
 for(int t=1;;t++)
 {
  for(int i=0;i<2002;i++)
    for(int j=0;j<2002;j++)
     dp[i][j]=-1;

  long long int  n,i,j;
  cin>>n;

  if(n==0) break;


  long long int  tot=0;

  for(i=1;i<=n;i++)
   {
       cin>>a[i];
       tot+=a[i];
   }

  long long int  kk=send(a,1,n);

 // cout<<abs(tot-kk-kk)<<endl;
  cout<<"In game "<<t<<", the greedy strategy might lose by as many as "<<abs(tot-kk-kk)<<" points."<<endl;

   /* for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)
      cout<<dp[i][j]<<" ";
       cout<<endl;*/



 }
return 0;
}