Question

求助15年省赛c语言B组第九题 垒骰子

Answer 1

看了一下题目，说一下我的初期想法，没实现，只是想法。
用动态规划做。
动态转移方程：
A[i][j]:代表共i个骰子，最高的一个以j向上共有A[i][j]个叠法
假设j的对面是k，而可以和k相贴的有O，P，T
那么A[i][j]=（A[i-1][O]+A[i-1][P]+A[i-1][T])）*4
为什么乘4？因为当个骰子以j向上有4种（想象一下，假设东面是k，将k转到西，南，北就有三种，加上东面就是4种）
而骰子的叠法共有A[n][1]+A[n][2]+A[n][3]+A[n][4]+A[n][5]+A[n][6]种
时间复杂度：从下（i=1）往上（i=n）计算A[i][j]的值，最糟糕的情况下计算A[n][1]需要进行6*（n-1）次运算（A[n][2]，A[n][3].。。。等等都一样），那么一共需要进行6n次运算
也就是时间复杂度是线性的，效率应该可以了。对于100% 的数据应该也能通过。
另外问：这题哪个oj系统有？我去做做，看能不能通过。