➤ Problem Link : TWENDS
👉 Hint : Use DP and Greedy approach
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int arr[1000];
int f(int i,int j)
{
if(i==j)
return 0;
if(arr[i]>=arr[j])
return dp[i+1][j];
else if(arr[i]<arr[j])
return dp[i][j-1];
}
int main()
{
int k=0;
while(1)
{
++k;
int n;
cin>>n;
if(n==0)
break;
bool a2[n];
memset(a2,0,sizeof(a2));
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
for(int i=0;i<n;i++)
{
dp[i][i]=arr[i];
}
int greedy=0;
for(int k=1;k<n;k++)
{
int i,j;
for(i=0,j=k;i<n,j<n;i++,j++)
{
dp[i][j]=max(arr[i]+f(i+1,j),arr[j]+f(i,j-1));
}
}
int i=0,j=n-1;
while(i<j)
{
if(dp[i][j]==arr[i]+f(i+1,j))
{
if(arr[i+1]>=arr[j])
{
greedy+=arr[i+1];
i+=2;
}
else
{
greedy+=arr[j];
i++;j--;
}
}
else
{
if(arr[i]>=arr[j-1])
{
greedy+=arr[i];
i++;j--;
}
else
{
greedy+=arr[j-1];
j-=2;
}
}
}
cout<<"In game "<<k<<", the greedy strategy might lose by as many as "<<dp[0][n-1]-greedy<<" points."<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.