### eagle93's blog

By eagle93, 7 years ago,

I've tried the brute force approach, but TLE for sure :P

Any hints will be appreciated!

• +5

 » 7 years ago, # |   0 It's DP problem. D(L, R).
•  » » 7 years ago, # ^ |   +1 but how will you manage the cuts?if n = 5, and you choose L=0, R=5how will you manage the remaining sub-polygons?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 ok. DP(L, R, numberOfCuts) int cuts = n / 2 +-1; for (i = 0; i < n; ++i) for (int j = i; j < n; ++j) for (int k = 0; k <= cuts; ++k) res = min(res, D(i, j, k) + D(j, i, cuts - k)); UPD: just DP(0, 1, cuts). I'm an idiot
•  » » » » 7 years ago, # ^ |   0 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 :)
•  » » » » » 7 years ago, # ^ |   +3 Code below DP function declaration is in int main() body of DP function you should write. first cut was in main. 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)...
•  » » » » » 7 years ago, # ^ |   +3 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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +1 int remaining(int L, int R) { int res = 0; while (L != R) { ++res; L = (L + 1) % n; } return res / 2 -2; } 
 » 7 years ago, # |   +2 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!
 » 7 years ago, # |   0 Hi All, Please, I need some hints to solve cut(12800) problem
 » 7 years ago, # | ← Rev. 2 →   +3 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