NC16665 [NOIP2005]过河（状压dp）

题意

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

数据范围

对于30%的数据，；
对于全部的数据，,，。

分析

当 和 之间的距离 大于某个值时，青蛙肯定能跳到 前面 的位置。
大胆预测，这个值不超过 。其实比较容易证明，但这里略去。。。
于是当 时，我们让 。这样就把 从 降到了 ，变成一道完全可做题。
特别要注意的是要特判 的情况，否则只有

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 105
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int a[N], b[N], stone[100005], f[100005];
int main(){
    int i, j, n, m, L, s, t;
    L = read();
    s = read(); t = read(); n = read();
    for(i = 1; i <= n; i++) a[i] = read();
    if(s == t){
        int tot = 0;
        for(i = 1; i <= n; i++) tot += (a[i] % s == 0);
        printf("%d", tot), exit(0);
    }
    sort(a + 1, a + i);
    b[1] = min(100, a[1]);
    for(i = 2; i <= n; i++){
        if(a[i] - a[i - 1] >= 100){
            b[i] = b[i - 1] + 100;
        }
        else b[i] = b[i - 1] + a[i] - a[i - 1];
    }
    for(i = 1; i <= n; i++) stone[b[i]]++;
    memset(f, 1, sizeof(f));
    f[0] = 0;
    for(i = s; i <= 100000; i++){
        for(j = s; j <= t; j++){
            if(i - j >= 0) f[i] = min(f[i], f[i - j] + stone[i]);
        }
    }
    printf("%d", f[100000]);
    return 0;
}