比赛 状态压缩DP练习 评测结果 AAAAAAAAAA
题目名称 过河 最终得分 100
用户昵称 Hale 运行时间 0.039 s
代码语言 C++ 内存使用 16.33 MiB
提交时间 2019-05-28 17:32:21
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int a[105],d[105],stone[350000];
int f[350000]; 
int main()
{   freopen("river.in","r",stdin);
    freopen("river.out","w",stdout);
    int l,s,t,m;
    cin>>l>>s>>t>>m;
    for (int i=1;i<=m;i++)
        cin>>a[i];
    sort(a+1,a+m+1); 
    for (int i=1;i<=m;i++)
        d[i]=(a[i]-a[i-1])%2520; 
    for (int i=1;i<=m;i++)
    {
        a[i]=a[i-1]+d[i];
        stone[a[i]]=1; 
    }
    l=a[m]; 
    for (int i=0;i<=l+t;i++) f[i]=m; 
    f[0]=0;
    for (int i=1;i<=l+t;i++)
        for (int j=s;j<=t;j++)
        {
            if (i-j>=0)
                f[i]=min(f[i],f[i-j]);
            f[i]+=stone[i];
        }
    int ans=m;
    for (int i=l;i<l+t;i++) ans=min(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}