How could i solve this problem.Please help me to solve this problem. Thanks in advance :)
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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