码风幽默求帮助
查看原帖
码风幽默求帮助
987758
CaoSheng_zzz楼主2024/9/30 22:36
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#define prt printf
#define ll long long
#define spc putchar(' ')
#define ent putchar('\n')
#define pr_ prt("---")
#define prx prt("***")
#define prtn (putchar('N') , putchar('o'))
#define prty (putchar('Y') , putchar('e') , putchar('s'))

inline ll read() {
    bool f = 1 ; ll k = 0;
    char c = getchar() ;
    while(c < '0' || c > '9') {
        f = c == '-' ? 0 : 1 ;
        c = getchar() ;
    }
    while(c >= '0' && c <= '9') {
        k = (k << 3) + (k << 1) + (c ^ 48);
        c = getchar() ;
    }
    return (f == 1 ? k : -k);
}

void output(ll now) {
    if(now < 0){
        putchar('-');
        output(- now);
    }
    else{
        if(now > 9) output(now / 10);
        putchar((now % 10) ^ 48);
    }
}

inline ll max(ll a , ll b) { return a > b ? a : b ;}
inline ll min(ll a , ll b) { return a < b ? a : b ;}

const int maxn = 1e4 + 1 , maxm = 1e2 + 1  ;
bool flag[maxn] ;
int L , S , T , M ;
int d[maxm] ;
int f[maxn] ;

signed main() {
    L = read() ;
    S = read() , T = read() , M = read() ;
    for(int i=1 ; i<=M ; i++) d[i] = read() ;
    std::sort(d + 1 , d + M + 1) ;
    if(S == T) {
        int ans = 0 ;
        for(int i=1 ; i<=M ; i++) if(! (d[i] % S)) ++ ans ;
        return output(ans) , 0 ;
    }
    for(int i=1 ; i<=M ; i++) {
        if(d[i] - d[i - 1] >= S * T) d[i] = d[i - 1] + (S * T) ;
        flag[d[i]] = true ;
    }
    memset(f , 0x3f , sizeof f) ;
    f[0] = flag[0] ;
    for(int i=0 ; i<=d[M] ; i++) {
        for(int k=S ; k<=T ; k++) {
            f[i + k] = min(f[i + k] , f[i] + flag[i + k]) ;
        }
    }
    int ans = 101 ;
    for(int i=d[M] ; i<=d[M]+T ; i++) ans = min(ans , f[i]) ;
    return output(ans) , 0 ;
}
2024/9/30 22:36
加载中...