NOIP2005提高組 过河 river 解題報告

【問題描述】

在河上有一座獨木橋，一隻青蛙想沿着獨木橋從河的一側跳到另一側。在橋上有一些石子，青蛙很討厭踩在這些石子上。由於橋的長度和青蛙一次跳過的距離都是正整數，我們可以把獨木橋上青蛙可能到達的點看成數軸上的一串整點： 0 ， 1 ，……， L （其中 L 是橋的長度）。座標爲 0 的點表示橋的起點，座標爲 L 的點表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是 S 到 T 之間的任意正整數（包括 S,T ）。當青蛙跳到或跳過座標爲 L 的點時，就算青蛙已經跳出了獨木橋。

題目給出獨木橋的長度 L ，青蛙跳躍的距離範圍 S,T ，橋上石子的位置。你的任務是確定青蛙要想過河，最少需要踩到的石子數。

【輸入文件】

輸入文件的第一行有一個正整數 L （ 1 <= L <= 10^9 ），表示獨木橋的長度。第二行有三個正整數 S ， T ， M ，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數，其中 1 <= S <= T <= 10 ， 1 <= M <= 100 。第三行有 M 個不同的正整數分別表示這 M 個石子在數軸上的位置（數據保證橋的起點和終點處沒有石子）。所有相鄰的整數之間用一個空格隔開。

【輸出文件】

輸出文件只包括一個整數，表示青蛙過河最少需要踩到的石子數。

【輸入輸出樣例】

river .in

10

2 3 5

2 3 5 6 7

river .out

2

【數據規模】

對於30%的數據，L <= 10000；

對於全部的數據，L <= 10^9。

【分析】

以下題解来自：http://www.byvoid.com/blog/noip-allsolutions/

動態規劃，需要狀態壓縮。

狀態

F[i] 跳到距離i處碰到的最少的石子數。

狀態轉移方程

F[i]=min{ F[i-k] } + F[i] (S<=k<=T i-k>=0)

邊界條件

F[i]=1 i處有石子

目標結果

min{ F[k] } (L+1<=k<=L+T-1)

狀態壓縮

由於L最大爲10^9，直接綫性遞推會超時。發現石子數很少，這意味着路徑上有許多很長的空白段。我們可以把長度大於S*T的空白段都縮小到S*T，這樣最長只有10090了。

【我的代碼】

//NOIP2005 river
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;
ifstream fin("river.in");
ofstream fout("river.out");
int F[100000]={0};
int stone[1000];
int maxd, //每次跳跃的最大距离
    mind, //每次跳躍的最小距離
    S,  //石子的长度
    L;  //独木桥的长度
   
int Compare(const void *elem1, const void *elem2)
{
    return *((int *)(elem1)) - *((int *)(elem2));
}     

void init()
{
    fin>>L;
    fin>>mind>>maxd>>S;
    for(int i=1;i<=S;i++)
    {
        fin>>stone[i];
    }
    fin.close();
}   


void compress()
{
    int p=maxd*mind;
    int k;
    stone[0]=0;
    stone[S+1]=L;
    for (int i=1;i<=S+1;i++)
    {
        if (stone[i]-stone[i-1]>p)
        {
            k=stone[i]-stone[i-1]-p;
            for (int j=i;j<=S+1;j++)
                stone[j]-=k;
            stone[i]=stone[i-1]+p;
        }
        F[stone[i]]=1;
    }
    L=stone[S+1];
}

void dp()
{
    int best;
    for (int i=1; i<=L+maxd-1; i++)
    {
        best=0xfffffff;
        for (int k=mind;k<=maxd;k++)
        {
            if (i-k>=0)
            {
                if (best>F[i-k])
                    best=F[i-k];
            }
        }
        F[i]+=best;
    }
}

int main()
{
    init();
   
    if (maxd==mind)
    {
        int best=0;
        for (int i=1;i<=S;i++)
            if (stone[i]%mind==0) best++;
        fout<<best<<endl;
        return 0;
    }
   
    qsort(stone+1,S,sizeof(int),Compare);
    compress();
       
   
    dp();
    int best=0xfffffff;
    for (int k=L+1;k<=L+maxd-1;k++)
    {
        if (best>F[k])
            best=F[k];
    }
    fout<<best<<endl;
    return 0;
}