洛谷1052——過河（DP+狀態壓縮）

題目描述

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

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

輸入輸出格式

輸入格式：

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

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

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

輸出格式：

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

輸入輸出樣例

輸入樣例#1：

10
2 3 5
2 3 5 6 7

輸出樣例#1：

2

說明

對于30%的數據，$L\le 10000$；

對于全部的數據，L≤109L \le 10^9L≤109。

2005提高組第二題

思路

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

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

• 當$S=T$的時候，可以很容易得到：所有在$S$倍數位置上的點，都會走到，所以對該種情況進行特判

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

假設每次走$p$或者$p+1$步.我們知道$gcd(p,p+1)=1$.
由擴展歐幾里得可知，對于二元一次方程組：
$px+(p+1)y=gcd(p,p+1)$是有整數解的，即可得：$px+(p+1)y=s$是一定有整數解的。
設$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$來實現)，$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
即表示，當$s\le p\times (p+1)$時，$px+(p+1)y=s$有兩個非負整數解，每次走$p$步或者$p+1$步，$p\times (p+1)$之后的地方均能夠到達。
如果兩個石子之間的距離大于$p\times (p+1)$，那么就可以直接將他們之間的距離更改為$p\times (p+1)$。
綜上，得到壓縮路徑的方法：若兩個石子之間的距離大于$t\times (t?1)$，則將他們的距離更改為$t\times (t?1)$。

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

關于路徑壓縮常數的選擇，證明過程詳見：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;// 縮點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;
}