呵呵！感谢！ 原来是这么细微的问题！ 晕哦
谢谢哈
另外，你说的第二个问题是不存在的,我也考虑到你说的问题；因为你仍然用的
for(k=2;k<=n;k++)
for(i=1;i<k;i++)
for(j=1;j<k;j++)
仍然是完全穷举
时间效率上没有任何改进，反而因为重复计算降低了效率。
其实可以这样改，会提高一点点效率：
for(k=2;k<=n;k++)
for(i=1;i<k;i++)
for(j=i;i<k;j++)
假设i,j<k
f[i][j][k-1]表示状态: 三个车分别在i,j,k-1的位置
状态转移有三个,要么是从某车i开到k ,要么是j开到k,要么是k-1开到k(递推方式,每次加1)
所以状态转移方程是:
f[i][j][k-1]+d[i][k] -> f[j][k-1][k]
f[i][j][k-1]+d[j][k] -> f[i][k-1][k]
f[i][j][k-1]+d[k-1][k] -> f[i][k-1][k]
这是3维动态规划的基本模型
唉,不知道怎么过不去啊~
你要是有兴趣就帮忙测试一下吧~ 呵呵
@Run&Run
呵呵,其实很简单,你纸上画一下就知道了
s==0;for(i=2;i<=n;i++)s=(s+m)%i;
是指n个人,编号从0到n-1 .输出的时候必须输出s+1 (编号s的人是第s+1个人)
而s==1;for(i=2;i<=n-1;i++)s=(s+m-1)%i+1; ㈠是有n-1个人,编号是从1开始的(题目其实是除去了第一个人的约瑟夫问题,所以只有n-1个人);㈡从约瑟夫问题回归到在这道题中,发现编号并不是真正从1开始的,第一个人首先出去.所以依次向后移动一个编号,故也需要输出s+1 ,和上面的s+1不同,这一点注意.
我这样写是为了方便自己理解,当然从数学的角度,你完全可以化简它
其实我自己做的时候并没有注意到这些细节,也没有把两个s+1拿出去比较,这些东西也不是需要强记硬背的,重点还是要看透彻问题的本身
以上是一点心得,呵呵,谢谢关注,希望我的解答对你有帮助.
哦对了,注意两点.
一是数组定义一定要放在全局的位置,局部变量名字最好不要重复, 不知道为什么,否则有时通不过,很诡异..但是在自己的机器上测试却不存在这点
呵呵,这道题写得太快了,代码竟然这么多疏漏,,,虽然AC了,但是低级错误也不少