Game theory (dp +game theory )

                                                ww.spoj.com/problems/TRT/

         

TRT - Treats for the Cows

In this problem ,we have to maximize the result . at each chance the value becomes
(chance_number*value).we can pick either





#include<bits/stdc++.h>

using namespace std;

int dp[2005][2005];

int a[10000];

int cal(int a[],int st,int en,int cur)
{
 if(st>en)
    return 0;

 if(dp[st][en]!=-1)
    return dp[st][en];

 if(st==en)
 {
     dp[st][en]=a[st]*cur;
     return dp[st][en];
 }

 else
 {

 int ans1=a[st]*cur;
 ans1+=cal(a,st+1,en,cur+1);

 int ans2=a[en]*cur;
 ans2+=cal(a,st,en-1,cur+1);

 dp[st][en]=max(ans1,ans2);
 return max(ans1,ans2);

 }
}



int main()
{
 int n,i,j;
 cin>>n;

  for(i=0;i<2005;i++)
     for(j=0;j<2005;j++)
       dp[i][j]=-1;

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

  int k=cal(a,1,n,1);
  cout<<k<<endl;
return 0;
}