解题思路:
动态规划
建立一个大小为(m+1)*(maxnum)的二维数组dp。其中m代表r最多能划分的位数,maxnum代表r中每一位的最大值。
dp[i][j]代表r有i位,最高位为j时有多少种可能。
①初始化dp[1][j]=1(j = 1 to maxnum),1位时最高位最高位为j的可能数为1。
②由题意中任何一位数小于右边相邻的数。可以得出状态转移方程
dp[i][j] = dp[i][j]+dp[i-1][k](j<k<maxnum)
将i=2 to m进行更行。
其中r有j位时总的可能数为sum(dp[i])
注意:当有m位时要进行特殊处理,因为有m位时最高位并不一定能取到maxnum。令x=w%k,最高位只能取到2**x-1
③最后我们将r有i位(2<=i<=m)时的可能数求和即可。
注意事项:
参考代码:
def f(k,w): m = 0 #记录最多能划分的位数 if w % k == 0: m = w//k else: m = w//k + 1 maxnum = 2**k #记录每一位的最大值 dp = [[0 for j in range(maxnum)] for i in range(m+1)] for i in range(1,maxnum): #初始化dp[1][i]=1 dp[1][i] = 1 for i in range(2,m+1): #将i= 2 to m 时的情况进行更新 for j in range(1,maxnum-i+1): for k in range(j+1,maxnum-i+2): dp[i][j] = dp[i][j] + dp[i-1][k] ans = 0 x = w % k for i in range(2,m): ans = ans + sum(dp[i]) for i in range(1,2**x): ans = ans + dp[m][i] print(ans) if __name__ == '__main__': k,w = map(int,input().strip().split()) f(k,w)
0.0分
5 人评分
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:629 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C++代码)(手动优化一下计算)浏览:1284 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:676 |
输出九九乘法表 (C语言代码)浏览:1048 |
【计算球体积】 (C语言代码)浏览:1551 |
小九九 (C++代码)简单粗暴,直接输出浏览:665 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:497 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:3358 |
计算质因子 (Java代码)浏览:748 |
字符串比较 (C语言代码)浏览:1224 |