/ Vijos / 讨论 / 过河 /

为什么最后一组过不了?

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int l,s,t,m;
int map[1000005];
int k[1000005];
int pos[105];
int ans[1000005];
int min(int x,int y)
{
if(x<y)return x;
return y;
}
int main()
{
memset(ans,127,sizeof(ans));

scanf("%d%d%d%d",&l,&s,&t,&m);

int mod=s*t;

for(int i=1;i<=m;i++)

scanf("%d",&pos[i]);

sort(pos+1,pos+m+1);

int temp=0;

for(int i=1;i<=m;i++)

{

int cha=pos[i]-pos[i-1];

int qwe=cha;

cha%=mod; qwe/=mod;

temp+=cha;

if(qwe!=0)

temp+=mod;

k[temp]=1;

}

temp+=s*t;

for(int i=0;i<=s-1;i++)

ans[i]=0;

for(int i=s;i<=temp;i++)

{

for(int j=s;j<=t;j++)

{

if(i-j<0)break;

if(i-j>0&&i-j<s)continue;

ans[i]=min(ans[i-j]+k[i],ans[i]);

}

}

printf("%d",ans[temp]);

}

2 条评论

  • 1

信息

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