求助大佬,45分
查看原帖
求助大佬,45分
904155
wxc_1楼主2024/2/29 21:04
#include<bits/stdc++.h>
int dp[1000005];

int main()
{
    int l,s,t,m;
    int a[105];
    scanf("%d%d%d%d",&l,&s,&t,&m);
    if(l>1000005) l=1000005;
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    a[m+1]=l;
    std::sort(a+1,a+m+2);
    int ans=0xffff;
    if(s==t)
    {
        for(int i=1;i<=m;i++)
            if(a[i]%s==0)
                ans++;
            printf("%d",ans);
        return 0;
    }
    int dec=0;
    for(int i=1;i<=m+1;i++)  //缩点
    {
        a[i]-=dec;
        while(a[i]-a[i-1]>71)
            {a[i]-=71;dec+=71;}
    }
    int p=1;
    for(int i=s;i<=l;i++)
    {
        if(i>a[p]&&p<=m) p++;
        for(int j=s;j<=t;j++)
        {
            if(i-j<0) break;
            if(i-j<s&&i>s) {dp[i]=dp[i-1];continue;}
            if(a[p]==i) dp[i]=std::min(dp[i-j],dp[i-1])+1;
            else dp[i]=std::min(dp[i-j],dp[i-1]);
        }
    }
    for(int i=l-t;i<=l;i++)
        ans=std::min(ans,dp[i]);
     printf("%d",ans);

    return 0;
}
2024/2/29 21:04
加载中...