/ Vijos / 讨论 / 过河 /

这个程序哪里错了?

#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 条评论

  • @ 2013-08-17 10:46:11

    没有,可是现在是一组数据都没过,可是自己变得小范围数据都对。
    这是怎么回事?

    • @ 2013-08-17 11:01:13

      这个有没有加路径压缩?

    • @ 2013-08-17 11:05:15

      有啊,if(c[i]>2*t+1)c[i]=2*t+1;这步就是。就是把路径分段,大于一定值的就压缩。

    • @ 2013-08-17 11:06:10

      有没有qq,在qq上说吧。

    • @ 2013-08-17 11:14:44

      资料里有,加我一下吧……记得加备注……

    • @ 2013-08-17 11:19:21

      你这个路径压缩压得太狠了,压到300的距离就够了……

    • @ 2013-08-17 11:24:12

      怎么计算压缩路径啊?

    • @ 2013-08-17 11:54:22

      某个大神证明过最大300

    • @ 2013-08-17 11:59:15

      是所有的小段都压到三百以内吗

  • @ 2013-08-17 10:43:11

    你的程序输出有点错
    输入:
    1000000000
    3 3 2
    33333333
    999999999
    不知有没有考虑最小步数=最大步数?

  • 1

信息

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