【RQNOJ】PID17 / 过河

题目描述

　　在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

　　题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

　　对于30%的数据，L <= 10000；

　　对于全部的数据，L <= 10^9。
输入格式

　　输入的第一行有一个正整数L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

分析：
1. 由于M最大值限制在100，而L最大值为10^9，所以石头分步在数轴上必定是离散分步（局部可能密集）。
2. 对于任意三个点[A, B, C], 如果A与B的距离足够远，那么青蛙通过A点后，有足够的距离调整策略，可以顺利避开B点；同时，如果B与C足够远，那么青蛙通过B点后也有足够的距离调整策略避开C点。 对于青蛙最小步长S，最大步长T，这个“足够的距离”可以取S与T的最小公倍数（记为DMAX)。 
3. 基于2的分析，对于数轴上的离散点（前后距离都大于DMAX），这个点完全不影响前后点的策略，因此可以直接从目标点中删除。
4. 基于3，将数轴上所有离散点清理后，那么剩余的点就可以划分为一个一个的“密集群”，青蛙通过这个数轴需要踩踏石子的数量就是通过每一个密集区踩踏石子的数量累加和。
5.考虑青蛙通过一个密集区[s, l]：等价于青蛙的坐标大于或等于该密集区最大石头位置l；等价于，青蛙到达l，（l+1)，...,(l+T-1)这些坐标中任意一个。
6.设f(x)表示青蛙到达坐标x点最少需要踩踏的石子数目，那么f(x)的值取决于两点：其一，x坐标点是否有石子；其二上一个位置已经踩踏的石子数目。其中，上一个位置依据步长可能取值为(x-T),(x-T+1),...,(x-S)。那么依照题意，可以得出f(x)的递推公式为
        f(x) = min( f(x-T), f(x-T+1), ..., f(x-S) ) + L(x)，其中L(x)表示在x位置的石子数，取0或1
        f(0) = 0; f(X) = M(无穷大，表示不可达），其中X < 0 或 0         

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_M 100

/*
* 通过一段石头密集的区域，所必须踩踏的石子数目
* 由于默认是从桥头0位置开始，那么桥头起始部分位置(l < minStep )是不可达的，到达该位置踩踏的石子数记为最大石子数
*
*/
static int groupPass(int *stones, int start, int end, int minStep, int maxStep)
{
    int preindex = stones[start] >= maxStep ? maxStep : stones[start];
    int length = (stones[end] - stones[start] + 1) + preindex + (minStep - 1);
    int *index = (int*)calloc(sizeof(int), length);
    int cnt = MAX_M;

    int i;
    if (stones[start] < maxStep)
    {
        for (i = 1; i< minStep; i++)
        {
            index[i] = MAX_M;
        }
    }
    for (i = start; i <= end; i++)
    {
        if (stones[i])
        {
            index[ stones[i] - stones[start] + preindex] = 1;
        }
    }

    for (i = minStep; i < length; i++)
    {
        int j;
        int min = MAX_M;
        for (j = maxStep; j >= minStep; j--)
        {
            if (i - j >= 0)
            {
                min = min > index[i -j] ? index[i -j] : min;
            }
        }
        index[i] = min + index[i];
    }

    for (i = length -1; i >= length - minStep; i--)
    {
        cnt = index[i] > cnt ? cnt : index[i];
    }
    return cnt;
}

/**
 * step1, 清理孤立石子
 * step2，查找密集石子段的起点和终点，计算通过该段需要踩踏的最小石头数目，并累加到总数上
 * step3，从上一段的下一个石子位置开始，重复步骤2直到到达最后一个石子位置

 */
static int bridgePass(int *stones, int len, int minStep, int maxStep)
{
    int dist = minStep * maxStep;
    int gstart;
    int gend;
    int cursor;
    int i;

    int cnt = 0;
    int flag = 0; // 0, finding start; 1 finding end; 2 found group and processing

    if (NULL == stones || len <= 0 || minStep <= 0 || maxStep <= 0)
    {
        return -1;
    }

    if (minStep == maxStep)
    {
        for (i = 0; i < len; i++)
        {
            if (stones[i] % maxStep == 0)
            {
                cnt++;
            }
        }
        return cnt;
    }

    if (minStep > maxStep)
    {
        minStep = minStep + maxStep;
        maxStep = minStep - maxStep;
        minStep = minStep - maxStep;
    }

    cursor = 0;
    flag = 0;
    while (cursor < len)
    {
        if (flag == 0)
        {
            if (cursor + 1 < len && stones[cursor+1] - stones[cursor] < dist)
            {
                gstart = cursor;
                flag = 1;
            }
        }
        else if (flag == 1)
        {
            if (cursor + 1 == len || (cursor + 1 < len && stones[cursor+1] - stones[cursor] >= dist))
            {
                gend = cursor;
                cnt += groupPass(stones, gstart,gend,minStep,maxStep);
                flag = 0;
            }
        }
        cursor++;
    }

    return cnt;
}

int main(int argc, char **argv)
{
        int stones[] ={2,3, 5, 6, 7};
        printf("%d", bridgePass(stones, 5, 2, 3));
}