/ Vijos / 讨论 / 过河 /

评测机绝对是有问题的

初始化问题,看注释,Vijos的评测机没问题?你确定?
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
inline int min(int a,int b)
{
return a<b?a:b;
}
int f[20],a[200],L,S,T,M,p,c,ans=INT_MAX,now,tot;

int main()
{
int i,j;
scanf("%d%d%d%d",&L,&S,&T,&M);
for (i=0;i<M;i++)
scanf("%d",&a[i]);
if (S==T)
{
ans=0;
for (i=0;i<M;i++)
if (a[i]%T==0)
ans++;
printf("%d",ans);
return 0;
}
std::sort(a,a+M);
for(i=1;i<=T;i++)//初始化,用i<Tcase#3就wrong,但是f(T)是绝对用不到的,所有的f都modT了
{
f[i]=INT_MAX;
}
f[0]=0; now=0; tot=0;
for (i=1;i<L+T;i++)
{
for (j=S;j<=T;j++)
{
f[i%T]=min(f[i%T],f[(i-j+T)%T]);
}
if (a[p]==i)
{
f[i%T]++;
p++;
}
if (now==f[i%T])
{
tot++;
now=f[(i+1)%T];
}
else
{
now=f[i%T];
tot=0;
}
if (tot==T)
{
i+=(min(a[p]-T,L)-i)/T*T;
tot = 0;
}
}
for (i=0;i<T;i++)
{
ans=min(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}

4 条评论

  • @ 2015-01-08 15:33:06

    twd2把贵程序反复修改提交了15次,早就清楚了一切。
    所以....https://vijos.org/records/?pid=1002
    还是小心别被打脸....

  • @ 2015-01-07 20:00:59

    话不要乱说。
    到时候打脸了就不好了。

  • @ 2015-01-06 21:47:29

    话不要乱说。
    到时候打脸了就不好了。

    • @ 2015-01-06 22:56:19

      +1

    • @ 2015-01-07 08:31:05

      +1

    • @ 2015-01-07 10:39:44

      我更想知道原因,f(T)根本用不到,为什么会影响结果?
      评测机的话,真心怀疑,看看上个问题,i不设全局就错

    • @ 2015-01-07 22:08:05

      越界的时候很多事情都容易发生吧…………
      C++越界会自己覆盖一些奇怪的内存地址而且不抛出异常,如果自己写程序越界了会出很多奇怪的事情吧……
      最后标题和内容说得就好像要造个大新闻一样…………(论起一个好标题的重要性……

    • @ 2015-01-07 23:17:42

      我来给一点提示吧。

      我们的评测机开启了O2优化,所以未定义的行为可能和不开优化的时候不一样。

  • @ 2015-01-06 20:55:58

    实验表明,是你的问题。

    • @ 2015-01-07 10:38:01

      我也试了,f(T)不设会陷入死循环,原因是最后会用到a[M],越界了,但是这和f(T)没关系。
      应该加的是石子个数小于M个,而不是f(T)的问题。
      f(T)有没有不应该影响结果

  • 1

信息

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