比赛 |
状态压缩DP练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
过河 |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
0.008 s |
代码语言 |
C++ |
内存使用 |
14.42 MiB |
提交时间 |
2019-05-28 19:37:17 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int l,a[100010],f[100010],n=0,m,s,t,k[110],ans=999;
int main(){
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
scanf("%d",&l);scanf("%d%d%d",&s,&t,&m);
for(int i=1;i<=m;i++)scanf("%d",&k[i]);
if(s==t){ans=0;
for(int i=1;i<=m;i++)if(k[i]%s==0)ans++;
printf("%d",ans);
return 0;
}
sort(k+1,k+1+m);
for(int i=1;i<=m;i++)n+=min(100,k[i]-k[i-1]),a[n]=1;
for(int i=1;i<=n;i++)f[i]=110;
for(int i=s;i<=n;i++)
for(int j=max(0,i-t);j<=i-s;j++)
f[i]=min(f[i],f[j]+a[i]);
for(int i=n;i>n-t;i--)ans=min(ans,f[i]);
printf("%d",ans);
return 0;
}