NOIP2005 过河

题目

vijos1002

luogu1052

题解

很容易想到动态规划，即三十分做法

当L <= 10^9 时，一步一步推便显得非常不可取，注意到L很大，而石子数m不超过一百，所以实际上有很多不必要的位置被一点一点后推，考虑缩短相邻石子间距

注意，石子位置无序，特判s==t的情况

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define N 10500
#define mod 90
using namespace std;

int l,s,t,m,x[N],ans;
int f[N],flag[N];

int main()
{
	scanf("%d%d%d%d",&l,&s,&t,&m);
	memset(f,127,sizeof(f));f[0]=0;
	for(int i=1;i<=m;i++) scanf("%d",&x[i]);
	if(s==t)
	{
        for(int i=1;i<=m;i++)
            if(x[i]%s==0)ans++;
        cout<<ans;
        return 0;
    }
	sort(x+1,x+1+m);ans=(1<<30);
	for(int i=1;i<=m;i++)
	{
		int dis=x[i]-x[i-1];
		x[i]=x[i-1]+dis%mod;
		flag[x[i]]=1;
	}
	l=(l-x[m])%mod+x[m];
	for(int i=s;i<=l+t;i++)
		for(int j=s;j<=t;j++)
		if(i>=j) f[i]=min(f[i],f[i-j]+flag[i]);
	for(int i=l;i<=l+t;i++) ans=min(ans,f[i]);
	printf("%d",ans);
	return 0;
}