How could i solve this problem.Please help me to solve this problem. Thanks in advance :)
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
How could i solve this problem.Please help me to solve this problem. Thanks in advance :)
Name |
---|
It is just (A1 + 1)(A2 + 1)...(An + 1) - 1. Expand it for proof.
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?
Proof by induction on size of array.
It's true for size = 1. Inductive step : moving from i-1 to i, use the recurrence mentioned in NMouad21's comment.
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];
and finally, the answer is just ans[n] of course
Here's an example code: https://ideone.com/VbqE9b