[codevs1105][COJ0183][NOIP2005]過河

[codevs1105][COJ0183][NOIP2005]過河

試題描述

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

輸入

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

輸出

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

輸入示例

10
2 3 5
2 3 5 6 7

輸出示例

2

數據規模及約定

對于30%的數據，L<=10000；
對于全部的數據，L<=10⁹。

題解

L 比較小時，可以直接 dp：設 f(i) 表示到達位置 i 時最少踩過的石子數目。正解與它做法一樣，只是發現許多節點是不需要考慮的，所以我們可以忽略它們。暴力找一下 S, T 分別取 1~10 時的最大不可表數，發現只有 71，那么當相鄰兩個石子間距離超過 71 時，我們就可以將這個距離變成它對 71 取模再加上 2 倍的 71，最后暴力 dp 一下就好了。注意判斷 S = T 的情況。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;int read() {int x = 0, f = 1; char c = getchar();while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }return x * f;
}#define maxn 27280
int L, S, T, n, A[maxn], f[maxn];
bool has[maxn];void up(int& a, int b) {if(a < 0) a = b;else a = min(a, b);return ;
}int main() {L = read(); S = read(); T = read(); n = read();for(int i = 1; i <= n; i++) A[i] = read();sort(A + 1, A + n + 1);if(S == T) {int cnt = 0;for(int i = 1; i <= n; i++) if(A[i] % S == 0) cnt++;return printf("%d\n", cnt), 0;}int p = 0;for(int i = 1; i <= n; i++)if(A[i] - A[i-1] <= 71) p += A[i] - A[i-1], has[p] = 1;else p += (A[i] - A[i-1]) % 71 + 142, has[p] = 1;memset(f, -1, sizeof(f));f[0] = 0;for(int i = 0; i <= p + 1; i++) if(f[i] >= 0)for(int j = S; j <= T; j++) {int tmp = (i + j <= p + 1) ? i + j : p + 1;up(f[tmp], f[i] + has[tmp]);}printf("%d\n", f[p+1]);return 0;
}

?