HDU 1494 - Pao Pao Ka Ding Che
Problem : You can have no more than 14 energies. you make each step by gaining 1 energy and take a[i] time or taking 5 energy and take b[i] time. The moving is on a circle with L positions, you go around the cirlce for N rounds, the start point is given, and tell the minimum time. (1<=N, L<=100)
Solution : Stretch the circle to at most N*L positions. Then denote f[i][j] as the i-th step has completed, and there are j energies now, the minimum time has cost. Thus f[i][j]=min(f[i-1][j-1]+a[i], f[i-1][j+5]+b[i]).
Think : How to solve the problem when 1<=N, L<=10000. (f1[i][j]: start with i energy, end with j energy, the minimum time. f2[i][j]: the i-th circle ended, remains j energy, the minimum time.)