| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 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 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | nor | 155 |
| 5 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Can anyone help me with this problem? http://www.spoj.com/problems/COLORSEG/
It seems it requires some state space reduction/some clever optimisation or an entirely different approach.Have been trying this for quite a long time and no solution/hints are available anywhere.Would be grateful if anyone can help
What's wrong with dp(i, c1, c2) equals number of ways to properly assign colors to the first i segments in such a way that i - 2-th segment will receive color c2 and i - 1-th segment — color c1.
Also note that there are t < = 2500 test cases and time limit is 1 second. Each case runs in O(50 * 50 * 50) = O(1.25 * 1005), so solving all test cases should lead to TLE with that dp recurrence.
There is only 50 different test cases each with his own value of M, but N is meaningless since we can make precalc with N = 50.