darkworld1's blog

help

By darkworld1, history, 6 years ago, In English

hi everyone i am trying to solve a question . the question goes like this

you have given an array you have to maximize the cost factor of array and cost can be calculated in following way

COST = A*a[i]-B*a[j]+C*a[k]+D*a[l]+E*a[m] where i<j<k<l<m

now you have given A,B,C,D,E , maximize the cost of given array

sample test case n= 5

array = { 10 17 15 6 17}

A=8, B=5, C=4, D=6, E=9

Output is 172

..............................................................................

MY approach is simple i make a dp[n][4] and dp[i][0] calculate the max of A*a[i] till i , dp[j][1] calculate the max of A*a[i]-B*a[j] and so on ..

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by darkworld1 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by darkworld1 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

This is quite a short yet impolite way to ask a question since you just mention the problem and assume that the community will help you.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    i agree it is short but it explaining the hole question and why you think it is impolite way of asking question ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      You just state the problem with the title "help". You didn't say "please help" or anything like that. It will most likely lower the mood of people reading this post.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by darkworld1 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

I think DP works here

dp[pos][state] to determine what will be the result

for example dp[3][3] = max(dp[3][3],C*arr[3]+dp[2][2])

or dp[4][3] = max(dp[4][3],C*arr[4]+dp[3][2])

calculating from previous state.

and answer will be maximum of dp[i][5]

→ Reply