/ Vijos / 讨论 / 过河 /

第五个点为什么过不了啊 求解

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define maxn 10000001
#define maxm 200
#define maxint 2000000000
#define YS 105
int n,m,s,t,a[maxm]={0},f[maxn]={0};
int main()
{
cin>>n;
cin>>s>>t>>m;
for(int i=1;i<=m;i++) {scanf("%d",&a[i]);}
if(s!=t)
{
sort(a+1,a+m+1);
//for(int i=1;i<=m;i++) cout<<a[i]<<" ";
//cout<<endl;
for(int i=2;i<=m;i++) {if(a[i]-a[i-1]>YS) a[i]=a[i-1]+(a[i]-a[i-1])%YS;}
//for(int i=1;i<=m;i++) cout<<a[i]<<" ";
for(int i=1;i<=m;i++) f[a[i]]++;
for(int i=s;i<=a[m]+s;i++)
{
int best=maxint;
for(int j=i-s;j>=i-t;j--)
{
if(j<0||j<s) {if(best==maxint) best=0; break;}
if(f[j]<best) best=f[j];
}
f[i]+=best;
}
int ans=maxint;
for(int i=a[m];i<=a[m]+s;i++) {if(ans>f[i]) ans=f[i];}
cout<<ans<<endl;
}
else if(s==t)
{
int ans=0;
for(int i=1;i<=m;i++) if(a[i]%s==0) ans++;
cout<<ans<<endl;
}
//system("pause");
return 0;
}

1 条评论

  • 1

信息

ID
1002
难度
7
分类
动态规划 点击显示
标签
递交数
25194
已通过
4368
通过率
17%
被复制
64
上传者