luogu 1052 過河

​​http://www.elijahqi.win/archives/469​​​

題目描述

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

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

輸入輸出格式

輸入格式：

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

輸出格式：

輸出檔案river.out隻包括一個整數，表示青蛙過河最少需要踩到的石子數。

輸入輸出樣例

輸入樣例#1：

10

2 3 5

2 3 5 6 7

輸出樣例#1：

2

說明

對于30%的資料，L <= 10000；

對于全部的資料，L <= 109。

2005提高組第二題

狀壓dp 我自己本來dp就不熟，做狀态壓縮就更難了，從8.2飛機上到現在才算明白點hh

直接先行動态規劃，10^9是我們的極限資料，很顯然拿不到滿分，我們觀察m可以知道，石子總數非常少，可以說明，石子十分稀疏，那麼可以知道，中間很多狀态是沒有用的

我們考慮把石子距離大于t的部分壓縮成t+dis[]%t

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 110
inline int min(int x,int y){
    return x<y?x:y;
}
int l,stone[N],dis[N],a[11000],s,t,m,f[11000];
int main(){
    //freopen("1052.in","r",stdin);
//  freopen("1052.out","w",stdout);
    scanf("%d",&l);
    scanf("%d%d%d",&s,&t,&m);
    for (int i=1;i<=m;++i) scanf("%d",&stone[i]);
    std::sort(stone+1,stone+m+1);
    for (int i=1;i<=m;++i) dis[i]=stone[i]-stone[i-1];
    for (int i=1;i<=m;++i){
        if (dis[i]>t) dis[i]=dis[i]%t+t;
        stone[i]=stone[i-1]+dis[i];
        a[stone[i]]=1; 
    }
    l=stone[m]+(l-stone[m])%t+t;
    memset(f,0x7f,sizeof(f));f[0]=0;
    for (int i=1;i<=l+t-1;++i){
        for (int j=s;j<=t;++j){
            if (i-j>=0&&i-j<l)
            if (a[i]) f[i]=min(f[i],f[i-j]+1);else f[i]=min(f[i],f[i-j]);
        }
    }
    int ans=0x7fffffff;
    for (int i=l;i<=l+t-1;++i){
        ans=min(ans,f[i]);
    }
    printf("%d",ans);
    return 0;
}