青蛙過河
Time Limit: 1000 MS Memory Limit: 65535 K
Total Submit: 29(11 users) Total Accepted: 9(9 users) Special Judge: No
Description
在河上有一座獨木橋，一只青蛙想沿著獨木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨木橋上青蛙可能到達的點看成數(shù)軸上的一串整點：0，1，……，L（其中L是橋的長度）。坐標(biāo)為0的點表示橋的起點，坐標(biāo)為L的點表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是s到t之間的任意正整數(shù)（包括s,t）。當(dāng)青蛙跳到或跳過坐標(biāo)為L的點時，就算青蛙已經(jīng)跳出了獨木橋。


題目給出獨木橋的長度L，青蛙跳躍的距離范圍s,t，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。
Input
有多組測試數(shù)據(jù)。
對于每組測試數(shù)據(jù)，第一行四個正整數(shù)L, s, t, n（1 <= L <= 10^5, 1 <= s <= t <= 10，1 <= n <= 100），分別表示獨木橋的長度，青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數(shù)。第二行有n個不同的正整數(shù)分別表示這n個石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點和終點處沒有石子）。所有相鄰的整數(shù)之間用一個空格隔開。
Output
每組測試數(shù)據(jù)僅輸出一行，包括一個整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)。
Sample Input
10 2 3 5
2 3 5 6 7
Sample Output

2

                     

#include<stdio.h>
#include<string.h>
const int MAXN=100020;
int flag[MAXN];
int dp[MAXN];
int main()
{
    int L,s,t,n;
    int a;
    while(scanf("%d%d%d%d",&L,&s,&t,&n)!=EOF)
    {
        memset(flag,0,sizeof(flag));
        memset(dp,-1,sizeof(dp));//初始化，-1為不能到達的 
        //dp[i]表示到底 i  點需要經(jīng)過的最少石子數(shù)，-1表示不能到達 
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a);
            flag[a]=1;//有石子為1，否則為0 
        }    
        dp[0]=0;
        for(int i=s;i<=L+t-1;i++)
        {
            for(int j=i-t;j<=i-s;j++)// j 點跳到 i 點 
            {
                if(j>=0&&dp[j]!=-1)//j 點能夠跳到 
                {
                    if(dp[i]==-1)dp[i]=dp[j]+flag[i]; //第一次 直 接 給 值 
                    else if(dp[i]>dp[j]+flag[i]) dp[i]=dp[j]+flag[i];//找小的值 
                    
                }    
            }    
        }  
        int res=10000;
        for(int i=L;i<=L+t-1;i++)//L 到 L+t-1 中最小的非 -1 值 
        {
            if(dp[i]!=-1&&dp[i]<res) res=dp[i];
        }      
        printf("%d\n",res);
    }    
    return 0;
}

 

文章來源:http://www.cnblogs.com/kuangbin/archive/2012/02/27/2369901.html