http://poj.org/problem?id=2520

today, I have solved problem poj 2520: now I'll share my approach:

use dynamic programming dp[cost][pos1-pos2] maximum position it can reach with cost cost and difference of position is p

pos1-pos2. cost is the true cost plus estimation function which is equal to 3*(len[0]-pos1-(len[1]-pos2)),

for each cost we constraint lower_bound and upper_bound of pos1-pos2 is between (3*(len[0]-len[1])-cost)/6 and

(3*(len[0]-len[1]+cost)/6.. and upper_bound of cost is not exceed 30000.

so the total state of dp is not bigger than 1.5*10^8..

it can AC with some constant optimization..

http://poj.org/status?problem_id=2520&user_id=&result=&language=