Блог пользователя WARush143

POI — Vacation
Автор WARush143, история, 7 лет назад, По-английски

Hi,

I'm currently solving the problem Vacation ( http://main.edu.pl/en/archive/ontak/2010/wak ). I find these problems where every subarray of length n has to satisfy some property very challenging. I believe its DP, but I would appreciate anyones help on this problem.

Thanks

  • Проголосовать: нравится
  • +29
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whats the time limit?

→ Ответить
»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

Linear program(n<=200) : http://ideone.com/dVn1wb
Maximize c^T*x, subject to x>=0 and Ax<=B. Here x = [3*n variables denoting if i is taken or not], 3*n equations for x<=1, and 3*n-n+1 equations for each sub-array of the form of sum(n consecutive x_i)<=k. c[i] = a[i]; Maximum of 600 variables and 1001 equations is solvable pretty fast.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    I wonder what's wrong with this solution(why are people downvoting?). It gives AC on POI judge.

    → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

You can fix numbers of days taken in first third and second third. Then do dp through each of three thirds, in parallel, remembering how many days you took in each third so far. Because of fixed numbers you can take care of constraints as you do dp. Complexity is O(nk5) .

There is also more general solution using mincost maxflow. It's similar to http://www.spoj.com/problems/VOL/ and problem D from NEERC16.

→ Ответить