int solve(int id) {
if(id==n)
return 0;
int &d = dp[id];
if(~d) return d;
d = 0;
for(int i=id+1;i<n;i++) {
if(dis[i]-dis[id]>=k) {
d >?= val[id] + solve(i);
}
}
return d;
}
Its O(n^2), and Juver++, is very correct.
On Wed, Jan 5, 2011 at 10:22 PM, Decipher <ankurseth...@gmail.com> wrote:
> I think your solution will take O(n3) time , as it will require three
> loops . 1st for index i , 2nd for first max and 3rd for second max .
> Instead we should take :
> dp[i] = max(dp[j]) + p[i] , where j<i and m[i] - m[j] > k . Pls
> correct me if something is wrong .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
