本文共 616 字，大约阅读时间需要 2 分钟。

洛谷P1052 过河

思路

缩短距离

代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;long long a[210],b[210],c[20010],f[20010];int main(){   	ios::sync_with_stdio(false);	long long n,m,s,t,i,j,ans;	memset(f,0x7f7f7f7f,sizeof(f)),memset(c,0,sizeof(c));	for(cin>>n>>s>>t>>m,i=1; i<=m; i++)cin>>a[i];	if(s==t)	{   		for(ans=0,i=1;i<=m;i++)			ans+=(a[i]%s==0);		cout<
       
        n)f[n]=min(f[n],f[i]+c[n]);			else f[i+j]=min(f[i+j],f[i]+c[i+j]);	for(ans=0x7f7f7f7f,i=n; i<=n+t; i++)ans=min(ans,f[i]);	cout<