#include<stdio.h>
#define MAX 2010
#define loop(i,n) for(i=1;i<=n;i++)
#define max(a,b) a>b?a:b
int ans[MAX][MAX],ind;
int arr[MAX];
int calculate(int index, int start, int end)
{
if(index>ind)
return 0;
else if(ans[start][end]!=-100)
return ans[start][end];
return
(ans[start][end]=max(index*arr[start]+calculate(index+1,start+1,end),index*arr[end]+calculate(index+1,start,end-1)));
}
int main()
{
int i,j;
scanf("%d",&ind);
loop(i,ind)
scanf("%d",&arr[i]);
loop(i,ind)
loop(j,ind)
ans[i][j]=-100;
int a=calculate(1,1,ind);
printf("%d\n",a);
return 0;
}
On Sun, Mar 6, 2011 at 10:28 PM, Logic King <[email protected]>wrote:
> U didn't read my post completely.............i know the test cases where my
> code..........Actually i want the correct logic/solution for the
> solution........i know my code is wrong....i failed to apply DP in my
> code.....plz help !!
>
> On Sun, Mar 6, 2011 at 1:32 AM, Arpit Sood <[email protected]> wrote:
>
>> where is dp in your code ? btw, there is a spoj forum, you should search
>> over there and you will get the required test cases where your code fails.
>>
>> Cheers!
>>
>> On Sat, Mar 5, 2011 at 11:45 PM, Logic King
>> <[email protected]>wrote:
>>
>>> i tried to solve the problem on spoj https://www.spoj.pl/problems/TRT/
>>> the problem is based on DP
>>>
>>> i coded the problem as ----
>>>
>>> #include<iostream>
>>> #include<algorithm>
>>> #include<cstdio>
>>> int arr[2000];
>>> int main()
>>> {
>>> int i,l,r,age=1,n,sum=0;
>>> scanf("%d",&n);
>>> l=0,r=n-1;
>>> for(i=0;i<n;i++)
>>> scanf("%d",&arr[i]);
>>> for(i=0;i<n;i++)
>>> {
>>> if(arr[l]<=arr[r])
>>> {
>>> sum+=arr[l]*age;
>>> l++;
>>> age++;
>>> }
>>> else
>>> {
>>> sum+=arr[r]*age;
>>> r--;
>>> age++;
>>> }
>>> }
>>> printf("%d\n",sum);
>>> return 0;
>>> }
>>>
>>>
>>> but i am getting WA on submission....
>>> Actually my code fails on some of the test cases like
>>> INPUT-
>>> 6
>>> 21
>>> 31
>>> 12
>>> 3
>>> 4
>>> 33
>>>
>>>
>>>
>>> The algorithm i use would give 349 (21*1 + 31*2 + 12*3 + 3*4 + 4*5 +
>>> 33*6) as the answer.
>>>
>>> But the correct answer is 389 with sequence of picking as(33, 4, 3, 12,
>>> 21, 31).
>>>
>>> plz help me improve my algorithm !!
>>>
>>> thanking in advance
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Regards,
Arpit Sood
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
