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