过河72pts求调
查看原帖
过河72pts求调
1386960
one_of_the_person楼主2024/9/28 15:26
#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 -1;
    if(p==0)return 0;
    if(f[p]>-2)return f[p];
    f[p]=1005;
    for(int i=max(2,s);i<=t;i++){
        int b;
        if((b=dfs(p-i))>-1)f[p]=min(f[p],b+(a[p]?1:0));
    }
    if(f[p]==1005)f[p]=-1;
    return f[p];
}
int main(){
    memset(f,-2,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);
    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/9/28 15:26
加载中...