P1052-过河

 1 #pragma GCC optimize("Ofast")
 2 #include <bits/stdc++.h>
 3 #define maxn 13003
 4 #define _for(i,a,b) for(int i = (a);i < b;i ++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 inline ll read()
 9 {
10     ll ans = 0;
11     char ch = getchar(), last = ' ';
12     while(!isdigit(ch)) last = ch, ch = getchar();
13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
14     if(last == '-') ans = -ans;
15     return ans;
16 }
17 inline void write(ll x)
18 {
19     if(x < 0) x = -x, putchar('-');
20     if(x >= 10) write(x / 10);
21     putchar(x % 10 + '0');
22 }
23 int L,S,T,M;
24 int stone[103];
25 int bridge[103];
26 int dp[11004];
27 int stone2[11004];
28 int main()
29 {
30     L = read(); S = read(); T = read(); M = read();
31     _for(i,1,M+1)
32         stone[i] = read();
33     
34     sort(stone+1,stone+1+M);
35     if(S==T)
36     {
37         int rnt = 0;
38         _for(i,1,M+1)
39             if(stone[i]%T==0)
40                 rnt ++;
41         write(rnt);
42         return 0;
43     }
44     
45     _for(i,1,M+1)
46     {
47         int d = stone[i]-stone[i-1];
48         if(d>=100) d = 100;
49         bridge[i] = bridge[i-1]+d; 
50         stone2[bridge[i]] = 1;
51     }
52     L = bridge[M] + 100;
53     
54     memset(dp,0x7f,sizeof(dp));
55     dp[0] = 0;
56     
57     _for(i,1,L+1)
58         _for(j,S,T+1)
59             if(i - j >= 0)
60                 if(stone2[i])
61                     dp[i] = min(dp[i],dp[i-j]+1);
62                 else
63                     dp[i] = min(dp[i],dp[i-j]);
64     
65     int rnt = INT_MAX;
66     _for(i,bridge[M],L+1)
67         rnt = min(rnt,dp[i]);
68     
69     write(rnt);
70     return 0;
71 }