#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 <crazy.logic.k...@gmail.com>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 <soodfi...@gmail.com> 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 >> <crazy.logic.k...@gmail.com>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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.