題目描述

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

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

輸入輸出格式

輸入格式：

第一行有$1$個正整數(shù)L(1≤L≤109)L(1 \le L \le 10^9)L(1≤L≤109)，表示獨(dú)木橋的長度。

第二行有$3$個正整數(shù)$S,T,M$，分別表示青蛙一次跳躍的最小距離，最大距離及橋上石子的個數(shù)，其中$1\le S\le T\le 10$,$1\le M\le 100$。

第三行有$M$個不同的正整數(shù)分別表示這$M$個石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個空格隔開。

輸出格式：

一個整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)。

輸入輸出樣例

輸入樣例#1：

10 2 3 5 2 3 5 6 7

輸出樣例#1：

2

說明

對于30%的數(shù)據(jù)，$L\le 10000$；

對于全部的數(shù)據(jù)，L≤109L \le 10^9L≤109。

2005提高組第二題

思路

如果不考慮數(shù)據(jù)范圍的話，可以很快得出遞推關(guān)系式：$dp[i]=min(dp[i+k]+a[i])(S\le k\le T)$（$a[i]$為$i$點(diǎn)的石頭數(shù)$dp[i]$表示到達(dá)$i$點(diǎn)踩到的最少石頭數(shù)）

然鵝看了數(shù)據(jù)范圍后，時間和空間都是過不去的。所以需要選擇別的方法：

• 當(dāng)$S=T$的時候，可以很容易得到：所有在$S$倍數(shù)位置上的點(diǎn)，都會走到，所以對該種情況進(jìn)行特判

• 我們可以發(fā)現(xiàn)石子在橋上放置的是非常稀疏的，而且當(dāng)點(diǎn)的位置超過一定范圍，點(diǎn)都是可以跳到的。所以可以將石子所在的位置壓縮到這個范圍里去。將壓縮后位置儲存起來作為新的石頭的位置，按照這個位置進(jìn)行dp即可

假設(shè)每次走$p$或者$p+1$步.我們知道$gcd(p,p+1)=1$.
由擴(kuò)展歐幾里得可知，對于二元一次方程組：
$px+(p+1)y=gcd(p,p+1)$是有整數(shù)解的，即可得：$px+(p+1)y=s$是一定有整數(shù)解的。
設(shè)$px+(p+1)y=s$的解為：x=x0+(p+1)t,y=y0?ptx=x_0+(p+1)t,y=y_0?ptx=x0?+(p+1)t,y=y0??pt。令$0\le x\le p$(通過增減$t$個$p+1$來實(shí)現(xiàn))，$s>p\times (p+1)?1$，
則有：y=s?pxp+1≥s?p2p+1>p(p+1)?1?pxp+1≥0y=\dfrac {s-px}{p+1}\geq \dfrac {s-p^{2}}{p+1} >\dfrac {p\left( p+1\right) -1-px}{p+1}\geq 0y=p+1s?px?≥p+1s?p2?>p+1p(p+1)?1?px?≥0
即表示，當(dāng)$s\le p\times (p+1)$時，$px+(p+1)y=s$有兩個非負(fù)整數(shù)解，每次走$p$步或者$p+1$步，$p\times (p+1)$之后的地方均能夠到達(dá)。
如果兩個石子之間的距離大于$p\times (p+1)$，那么就可以直接將他們之間的距離更改為$p\times (p+1)$。
綜上，得到壓縮路徑的方法：若兩個石子之間的距離大于$t\times (t?1)$，則將他們的距離更改為$t\times (t?1)$。

因$為t\le 10$，因此我們可以直接將大于$10\times 9$的距離直接化為$90$.

關(guān)于路徑壓縮常數(shù)的選擇，證明過程詳見：https://blog.csdn.net/qq_34940287/article/details/77494073

AC代碼

/*************************************************************************> Author: WZY> School: HPU> Created Time: 2019-02-03 15:55:49************************************************************************/ #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ms(a,b) memset(a,b,sizeof(a)) #define INF 0x7f7f7f7f const int maxn=1e6+10; const int mod=1e9+7; using namespace std; int a[maxn]; int dp[maxn]; int vis[maxn]; int main(int argc, char const *argv[]) {ios::sync_with_stdio(false);cin.tie(0);int L;int ans=0;int s,t,m;cin>>L;cin>>s>>t>>m;for(int i=1;i<=m;i++)cin>>a[i];if(s==t){for(int i=1;i<=m;i++){if(a[i]%s==0)ans++;}cout<<ans<<endl;return 0;}sort(a+1,a+1+m);int _=90;int res=a[1]%_;vis[res]=1;// 縮點(diǎn)for(int i=2;i<=m;i++){res+=(a[i]-a[i-1])%_;vis[res]=1;}for(int i=res;i>=0;i--){dp[i]=INF;for(int j=s;j<=t;j++)dp[i]=min(dp[i],dp[i+j]+vis[i]);}cout<<dp[0]<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Friends-A/p/11054978.html

總結(jié)

以上是生活随笔為你收集整理的洛谷1052——过河（DP+状态压缩）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。