- 过河
- 2013-08-17 10:31:37 @
#include<iostream>
using namespace std;
int l,s,t,m,d;
int a[10000];
bool vi[10000]={0};
int b[200]={0};
int c[200]={0};
void init()
{
cin>>l>>s>>t>>m;
d=l;l=0;
for(int i=1;i<=m;i++)
{
cin>>b[i];
c[i]=b[i]-b[i-1];
}
}
int main()
{
init();
for(int i=1;i<=m;i++)if(c[i]>2*t+1)c[i]=2*t+1;
for(int i=1;i<=m;i++)
{
l+=c[i];
vi[l]=1;
}
if(d-b[m]>2*t+1)l+=2*t+1;
else l+=d-b[m];
for(int i=1;i<=l+t;i++)
a[i]=1000;a[0]=0;
for(int i=0;i<=l;i++)
{
for(int j=s;j<=t;j++)
{
if(vi[i]==1&&a[i+j]>a[i]+1)a[i+j]=a[i]+1;
if(vi[i]==0&&a[i+j]>a[i])a[i+j]=a[i];
}
}
int q=1000;
for(int i=l;i<=l+t-1;i++)
{
if(a[i]<q)q=a[i];
}
cout<<q;
return 0;
}
2 条评论
-
jlyzlyp LV 7 @ 2013-08-17 10:46:11
没有,可是现在是一组数据都没过,可是自己变得小范围数据都对。
这是怎么回事? -
2013-08-17 10:43:11@
你的程序输出有点错
输入:
1000000000
3 3 2
33333333
999999999
不知有没有考虑最小步数=最大步数?
- 1