dp boj1074 candy的魔法

Candy的魔法Submit: 717   Accepted:137Time Limit: 1000MS  Memory Limit: 65536KDescription
小蚂蚁的家在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);
    }
}