problem link: here
I've tried the brute force approach, but TLE for sure :P
Any hints will be appreciated!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 142 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 8 | maroonrk | 132 |
| 10 | qwexd | 129 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.09.2026 02:31:42 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
It's DP problem. D(L, R).
but how will you manage the cuts?
if n = 5, and you choose L=0, R=5
how will you manage the remaining sub-polygons?
ok. DP(L, R, numberOfCuts)
UPD: just DP(0, 1, cuts). I'm an idiot
your code doesn't use L or R !
also, in this case:
if we have already cut the two red lines, how will we calculate the sub-problem?
thanks in advance :)
Code below DP function declaration is in
int main()body of DP function you should write. first cut was inmain. There was update "just DP(0, 1, cuts). I'm an idiot". DP(0, 1, 3) cuts (1, 8) and calls DP(2, 7, 2)...Suppose you are calculating DP(L, R). You know the line from R to L may be a cut (a red line), the other lines of the polygon are actual edges. Also you know the R-L line has to be a part of one quadrilateral.
So for the transition, choose two more points x and y and form the quadrilateral R-L-x-y. You can see that the remaining subproblems will all have at most one cut.
what is the secret behind the negative votes, it's just a question! what does it mean? is the answer is "the question is too easy to answer it ?!" your negative vote has no mean. just makes the weak students frighten from asking again!
I solve this problem with a dp aprouch : the main idea is that we can define a poligon with two indexes lo , hi lo <= hi that means that we have a convex polygon from lo , lo + 1 , .. hi , lo (the last edge close the polygon) the we can cut between some pair of point of our current polygon (in this transicions we have to conserve that the two halfes of polygon (subproblems) have 2 * n points (n >= 2) )
Finaly we have a O(n^4) complexity.
UPD : Code