How could i solve this problem.Please help me to solve this problem. Thanks in advance :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | jiangly | 3578 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | tourist | 3565 |
8 | maroonrk | 3531 |
9 | Radewoosh | 3521 |
10 | Um_nik | 3482 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
How could i solve this problem.Please help me to solve this problem. Thanks in advance :)
Название |
---|
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