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
Whats the time limit?
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.
I wonder what's wrong with this solution(why are people downvoting?). It gives AC on POI judge.
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.