小蚂蚁的家在X轴的原点上，他的学校在X轴的N点上。
小蚂蚁从家里出发，沿X轴正方向前进（不能往回走），去学校里上课，他的本能速度是每两秒一个单位。由于小蚂蚁的速度之慢，老师担心他会迟到，就在途中的 某些点上放了具有魔法的糖果（每个位置要么没放，要么只放了一个），每个糖果有一定的魔法值b，他能使小蚂蚁将以每秒1个单位的速度移动b秒，在这个魔法 期间之内它只能向前移动，不能停下，也不能吃其他糖果。当然了，小蚂蚁可以自己选择是否要吃糖果，以及吃哪些位置上的糖果。他也只能朝向学校的方向走，而 不能掉头。
现在给出你学校的位置N，以及糖果的放置情况，请你计算小蚂蚁到达学校至少需要多久。
Input
多组数据测试。数据以两个0结束输入。
每组数据包括两部分：第一行两个整数N（1< N <= 1000000000），M(0 <= M <= 50)，N为学校的位置，M表示老师在途中放置的糖果的数目；
接下来的M行里，每行两个整数a（1<= a <= N），b（1<=b<=10000），a表示糖果位置，b表示对应糖果的魔法值。
Output
对每一组测试输出，输出小蚂蚁至少需要多少时间才能到达学校。每组数据的输出应该占一行。
Sample Input
7 2
2 2
3 4
5 3
3 1
1 2
4 2
0 0
Sample Output
10
7
dp问题.
从后往前反推，每次保存吃掉这个candy的最优值和不吃这个candy的最优值
假设现在位于P点，有下面两种情况需要考虑
1. 不吃这个candy，则以两秒的速度前进到下一个candy处，选择持或不吃的最大值。
2. 吃掉这个candy，则以一秒的速度前进直到停下来(加速过程中不能吃其他candy)，停下来之后又以两秒的速度往前前进到下一个candy，选择其最大值
将以上两个最优值存入P点位置的最优值(吃P点的candy和不吃P点的candy两种情况)
如此直到开始点，选最大值即可
代码如下：
#include#define EAT 0 #define NOT_EAT 1 #define MIN(a, b) ((a) < (b) ? (a) : (b)) typedef struct _candy { int position; int magic; }ST_CANDY; ST_CANDY candy[51]; int state[51][2]; int cmp(const void *a, const void *b) { ST_CANDY *pa = (ST_CANDY *)a; ST_CANDY *pb = (ST_CANDY *)b; return (pa->position - pb->position); } int bin_search(int front, int rear, int target) { int mid; while (front <= rear) { mid = (rear + front) / 2; if (candy[mid].position >= target) rear = mid - 1; else front = mid + 1; } return front; } int dp(int dst, int size) { int i, position, magic, eat, not_eat, speedup, forward_to, next_candy, next_candy_index; for (i=size-1 ; i>=0 ; i--) { position = candy[i].position; magic = candy[i].magic; /* not eat this candy */ next_candy_index = bin_search(0, size - 1, position + 1); not_eat = (candy[next_candy_index].position - position) * 2 + MIN(state[next_candy_index][EAT], state[next_candy_index][NOT_EAT]); state[i][NOT_EAT] = not_eat; /* eat this candy */ if (position + magic > dst) { state[i][EAT] = state[i][NOT_EAT]; continue; } forward_to = position + magic; if (forward_to > dst) forward_to = position; next_candy_index = bin_search(0, size - 1, forward_to); eat = forward_to - position + (candy[next_candy_index].position - forward_to) * 2 + MIN(state[next_candy_index][EAT], state[next_candy_index][NOT_EAT]); state[i][EAT] = eat; } } int main(int argc, char *argv[]) { int N, M, i, min; while (scanf("%d %d", &N, &M)) { if (0 == N && 0 == M) break; for (i=0 ; i<M ; i++) scanf("%d %d", &candy[i].position, &candy[i].magic); qsort(candy, M, sizeof(ST_CANDY), cmp); candy[M].position = N; state[M][EAT] = state[M][NOT_EAT] = 0; dp(N, M); min = MIN(state[0][EAT], state[0][NOT_EAT]); min += (candy[0].position - 0) * 2; printf("%d ", min); } }