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

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

How could i solve this problem.Please help me to solve this problem. Thanks in advance :)

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

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

It is just (A1 + 1)(A2 + 1)...(An + 1) - 1. Expand it for proof.

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

    sorry,,i can't get any proof though it works well :) Thank you .Could you please help me to get the proof of your solution?

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

You can solve it by a simple O(n) DP approach.

let's suppose we have the answer to the prefix array ending at i — 1. if we add one element, which is a[i] then the answer for the prefix ending at i is:

ans[i] = ans[i — 1] + ans[i — 1]*a[i] + a[i];

  • ans[i — 1] << case where we don't include a[i] in the previous calculated subsequences
  • ans[i — 1]*a[i] << case where we include it
  • a[i] << case where we take it alone

and finally, the answer is just ans[n] of course

Here's an example code: https://ideone.com/VbqE9b