点这里查看
讨论 / 怎么做啊？？
晓小吃迪 2010-10-24 03:03:00
点我顶贴 收藏 删除
我把公式推出来了，然后快速幂做的。。为什么得0分啊。。这题应该怎么做啊？？
#1 rommel1@2010-10-23 20:03:00
回复 删除
应该是dp吧 ，设f[i,j,0]为在i点左腿跳了j次，f[i,j,1]=i点右腿跳了j次；

f[i,j,0]=sum(f[i-j,k,1]) 1=<k<=m

f[i,j,1]=sum(f[i-j,k,0]) 1=<k<=m

最优解为sum{f[n,j,0]+f[n,j,1]}

#2 多维数组@2010-10-23 21:57:00
回复 删除
。。。。。。。。。。。。。。。。。只过了一个点

我的解法是

状态和楼上一样

F[i][j][0]=

F[i-1][j-1][0] (2<=j<=m)

F[i-1][1][1]+F[i-1][2][1]+...+F[i-1][m][1]

然后用 滚动数组 优化空间。

然后就光荣超时。

#3 purplef@2010-10-24 01:52:00
回复 删除
这个线性算法肯定过不了！（10^18很大的）

很有可能是用二分的方法...可惜我没想出来

#4 L.Lawliet@2010-10-24 03:03:00
回复 删除
看到很多人都是秒过 可能有数值数论解法、、
查看更多回复
提交回复