91pts,求调
查看原帖
91pts,求调
1386960
one_of_the_person楼主2024/10/1 09:02
#include<bits/stdc++.h>
using namespace std;
int l,m,s,t,b[300005]={},c[300005]={},f[300005]={},ba;
bool a[300005]={};
int dfs(int p){
    if(p<0)return 1061109567;
    if(p==0)return 0;
    if(f[p]<=m)return f[p];
    for(int i=max(2,s);i<=t;i++){
        f[p]=min(f[p],dfs(p-i)+(a[p]?1:0));
    }
    return f[p];
}
int main(){
    memset(f,0x3f,sizeof(f));
    cin>>l>>s>>t>>m;
    ba=s*t;
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    sort(b+1,b+1+m);
    if(s==t){
        int ans=0;
        for(int i=1;i<=m;i++){
            if(b[i]%s==0)ans++;
        }
        cout<<ans;
        return 0;
    }
    for(int i=1;i<=m;i++){
        int d=b[i]-b[i-1];
        if(d>ba)d=ba;
        c[i]=c[i-1]+d;
        a[c[i]]=1;
    }
    l=c[m]+ba;
    int ans=1005;
    for(int i=l;i<=max(l+t-1,l);i++){
        ans=min(ans,dfs(i));
    }
    cout<<ans;
    return 0;
}
2024/10/1 09:02
加载中...