[vijos1002][NOIP2005]过河

Description

给定一条数轴，起点为0，数轴的某些整数点上有石子。每次可以移动的区间为[S,T]。求当到达或超过L时，最少踩到的石子数。

Input

输入的第一行有一个正整数L(1 <= L <= 10⁹)。

第二行有三个正整数S,T,M，M表示桥上石子的个数，其中1 <= S <= T <= 10,1 <= M <= 100。

第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的0和L处没有石子)。所有相邻的整数之间用一个空格隔开。

Output

输出只包括一个整数，表示最少踩到的石子数。

Sample Input

2 3 5

2 3 5 6 7

Sample Output

Solution

首先列出dp方程，f[i]表示到达i时最少踩到的石子数，则f[i]=min(f[i-k])(S<=k<=T)。

然后发现数据范围是10⁹，所以需要状压一下。

经过思考可以发现，如果在k+S×T和k+S×T+x(k>=0,x>0)处有石子，则若存在一种方案可以越过k+S×T，那么也能越过k+S×T+x。

具体证明时把S×T看成T个S相加，易证能到达k+S×T，也能到达k+S×T+x。

所以只需将距离超过S×T的石子距离缩到S×T就可以了。

 1 #include<cmath>
 2 #include<ctime>
 3 #include<queue>
 4 #include<stack>
 5 #include<cstdio>
 6 #include<vector>
 7 #include<cstring>
 8 #include<cstdlib>
 9 #include<iostream>
10 #include<algorithm>
11 #define M 101
12 #define L 20001 
13 using namespace std;
14 int a[M],f[L],l,m,s,t;
15 bool sto[L];
16 inline void init(){
17     scanf("%d%d%d%d",&l,&s,&t,&m);
18     for(int i=1;i<=m;i++)
19         scanf("%d",&a[i]);
20     sort(a+1,a+1+m);
21     if(s==t){
22         for(int i=1;i<=m;i++)
23             if(!(a[i]%s)&&a[i]<=l)
24                 f[0]++;
25         printf("%d
",f[0]);
26         return;
27     }
28     for(int i=1,d;i<=m;i++){
29         if(a[i]-a[i-1]>s*t){
30             d=a[i]-a[i-1]-s*t;
31             for(int j=i;j<=m;j++)
32                 a[j]-=d;
33         }
34         sto[a[i]]=true;
35     }
36     if(l-a[m]>s*t) l=a[m]+s*t;
37     fill(f+1,f+1+l,M);
38     for(int i=s;i<=l;i++){
39         f[i]=f[i-s];
40         for(int j=min(t,i);j>=s;j--)
41             f[i]=min(f[i],f[i-j]);
42         f[i]+=sto[i];
43     }
44     printf("%d
",f[l]);
45 }
46 int main(){
47     freopen("river.in","r",stdin);
48     freopen("river.out","w",stdout);
49     init();
50     fclose(stdin);
51     fclose(stdout);
52     return 0;
53 }