鏈接：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 131072K，其他語言262144K 64bit IO Format: %lld

題目描述

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

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

輸入描述:

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

輸出描述:

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

示例1
輸入

10 2 3 5 2 3 5 6 7

輸出

2

備注:
對于30%的數據，L<=10000；

對于全部的數據，L<=10⁹。

題解：

首先肯定是想到dp
dp[i]表示走到i這個位置的最小的踩石頭的次數
當從位置j調到位置i后，
如果當前位置i沒有石頭 f [ i ] = min ( f [ i ] , f [ j ] )
如果當前位置i有石頭：f[i] = min ( f [ i ], f [ j ] + 1)
就就這樣嗎？
并不是，看看數據范圍，開數組肯定爆了，這是在逼我們做優化
我注意看除了L之外的其他數據，相比之下S，T，M都夠小的，像S，T才0到10，那兩個石頭之間距離很大的話，我們可以調整步伐使得不踩到石頭如果這樣考慮，兩個距離很遠的石頭之間，我們可以到達任意距離。那距離再長又有何影響。
那我就要考慮兩個石頭之間距離達到多少才算大呢？
[S,T]是跳躍的范圍
當距離Len大于S * T時，len都至少有兩種方法可以跳到，（因為S * T等于T個S相加或者S個T相加），之后的距離都可以在修改之前的基礎上得到實現。說白了就是距離大于ST之后，都可以到達，那我們把距離大的都縮小到ST，這樣L的范圍不就限制住了嘛
回歸本題,S和T不重復時，S最大是9，T最大是10，S * T最大是90，也就是距離大于90的兩個石頭
所以我們只需將每兩個石頭超過 S * T 的距離縮成S * T就可以了

當S=T時，只需要枚舉每個石頭的坐標是否為s的倍數即可

代碼

含注釋

#include<bits/stdc++.h> using namespace std; const int maxn = 90 * 105;int s[maxn],a[maxn]; int dp[maxn],len;bool f[maxn]; //標記改點是否為石頭 memset(dp,0x7f,sizeof(dp)); int main() {int L,s,t,m;cin >> L >> s >> t >> m;len = s * t;for(int i = 1 ; i <= m ; ++ i)cin >> s[i];sort(s + 1,s + 1 + m);if(s == t)//當s與t重復時 {int sum =0;for(int i = 1 ; i <= m ; ++ i)if(s[i] % s == 0)sum++;printf("%d",sum);return 0;}for(int i = 1 ; i <= m ; ++ i){int d = s[i] - s[i - 1];//兩個石頭之間的距離 if(d >= len)d = len;//過大的距離進行更新 a[i] = a[i - 1] + d;//將新的石頭之間的距離更新到數組a中 f[a[i]] = 1;//更新新的石頭 if(i==m)L = a[m] + len;//根據最后一個石頭來重新更新獨木橋的長度 }dp[0] = 0;for(int i = 1 ; i <= L ; ++ i)for(int j = s ; j <= t ; ++ j){if(i >= j){if(f[i])dp[i] = min(dp[i - j] + 1,dp[i]);else dp[i] = min(dp[i - j],dp[i]);}}int ans = 200;for(int i = a[m] ; i <= L ; ++ i)ans = min(ans,dp[i]);cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的牛客网 【每日一题】5月9日 过河的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。