记录编号	566491	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	冷月星云	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2021-11-09 20:11:39	内存使用	5.85 MiB

#include<bits/stdc++.h>
using namespace std;
int l,s,t,m,a[200],f[10200],flag[10010],far[10010];
int main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	cin>>l>>s>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	sort(a+1,a+m+1);//注意石子并没有排序 
	if(s==t){
		int feiwu=0;
    	for(int i=1;i<=m;i++){
            if(a[i]%s==0){
                feiwu++;
            }
        }
        cout<<feiwu;
        return 0;
	} 
	int p=0;
	a[0]=0;f[0]=0;
	for(int i=1;i<=m;i++){
		far[i]=min(a[i]-a[i-1],90);
		p+=far[i];
		flag[p]=1;
	} //将每一个石子压缩并赋值
	far[m+1]=min(p-a[m],100);
	for(int i=1;i<=p+9;i++){
		f[i]=0x3f3f3f3f;
		for(int j=s;j<=t;j++){
			if(i>=j){
				f[i]=min(f[i],f[i-j]+flag[i]);
			}
		}
	}//核心dp 
	int ans=0x3f3f3f3f;
	for(int i=p;i<=p+9;i++){
		ans=min(ans,f[i]);
	} 
	cout<<ans;
}