比赛 状态压缩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;
}