Блог пользователя darkworld1

Автор darkworld1, история, 6 лет назад, По-английски

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 ..

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

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]