P1052-过河

痛定思痛。 2023-06-01 08:52 22阅读 0赞

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 }

转载于:https://www.cnblogs.com/Asurudo/p/11353329.html