P1052 [NOIP2005 提高组] 过河

[P1052 NOIP2005 提高组] 过河 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

问题描述：给定长度L，和一次可以跳动的长度 s 到 t，给定m个石头的位置，求最少经过多少个石头可以超过L。

思路：如果L很小的话，就是简单dp。
$$\begin{gathered} ifi有石头F(i)=min(F(i),F(i-j)+1)j\in [s,t] \\ elseF(i)=min(F(i),F(i-j))j\in [s,t] \end{gathered}$$
但是发现，L特别大，但是石头个数却特别小，同时也发现s和t也很小，就算m * t * s最大也才1000。如果将石头距离进行缩小就可以过。

对于 两个石头距离大于s * t的来说，对于区间[s * t, 两个石头之间的距离]都是可以经过跳[s, t]这些个数给到达的。因此，可以将两个石头距离大于s * t的缩小为s * t，这样就可以用上面的状态转移方程。

缩点

    int st = s * t;rep(i,1,m) {int dist = a[i] - a[i-1];if(dist >= st) dist = st;ph[i] = ph[i-1] + dist;// 将石头所在的那个点进行赋值为 truevis[ph[i]] = 1;}

状态转移方程

    int len = ph[m] + st; memset(f, 0x3f, sizeof(f));f[0] = 0;rep(i,1,len) {rep(j,s,t) {if(i - j >= 0) {if(vis[i]) f[i] = min(f[i-j] + 1, f[i]);else f[i] = min(f[i-j], f[i]);}}}

求答案

    int ans = INF;rep(i,ph[m],len) {ans = min(ans, f[i]);}

对s == t进行特判

    if(s == t) { // 特判 s == tint cnt = 0;rep(i,1,m) if(a[i] % s == 0) cnt++;cout<<cnt;return ;}

AC代码

const int N = 2e5 + 21;
int a[N], f[N],ph[N];
bool vis[N];
void solve() {int L,s,t,m; cin>>L>>s>>t>>m;rep(i,1,m) cin>>a[i];// 需要进行排序，石头位置初始是无序的sort(a+1, a+m+1);if(s == t) { // 特判 s == tint cnt = 0;rep(i,1,m) if(a[i] % s == 0) cnt++;cout<<cnt;return ;}// 如果 两个石头之间的距离大于等于 s * t，进行缩点/*** 因为，假设 两个石头距离为 len* 如果 len > s * t，则在 [s*t, len] 这个区间内的每一个点都可以访问到*/int st = s * t;rep(i,1,m) {int dist = a[i] - a[i-1];if(dist >= st) dist = st;ph[i] = ph[i-1] + dist;// 将石头所在的那个点进行赋值为 truevis[ph[i]] = 1;}// 因为是大于L就行，因此可能有超过L，但是是最小次数的情况int len = ph[m] + st; memset(f, 0x3f, sizeof(f));f[0] = 0;rep(i,1,len) {rep(j,s,t) {if(i - j >= 0) {if(vis[i]) f[i] = min(f[i-j] + 1, f[i]);else f[i] = min(f[i-j], f[i]);}}}int ans = INF;rep(i,ph[m],len) {ans = min(ans, f[i]);}cout<<ans;
}