tym777

用户名：timorthy7

访问量：4956

签　名：

老菜鸡了ToT

等　　级
排　　名	4050
经　　验	1702
参赛次数	0
文章发表	16
年　　龄	0
在职情况	学生
学　　校	仙交
专　　业	软件工程

　　自我简介：

TA的其他文章

1434: 蓝桥杯历届试题-回文数字
浏览：230

1433: 蓝桥杯2013年第四届真题-危险系数
浏览：260

蓝桥杯2013年第四届真题-剪格子 python实现 75%错误的解决方案。
浏览：121

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

优质题解

1110: 2^k进制数,动态规划dp解决！

　　作者: tym777　　　　发表时间：2021-10-31 15:24:30 浏览：1571　|　评论：0　

原题链接：2^k进制数

##解题思路：
利用动态规划的思想：
二维矩阵的dp[i][j]值的含义是：当一共有（i+1）位数字且最高位数字位数字是j的时候满足条件的数字总个数是多少。
###初始条件：
dp[0][]=1  即只有一位数字时只有一种情况
i 是2^k进制数下数字的位数，取w/k 向上取整，共（w/k 向上取整）行
j 是每一位上可以取到的值。为0到2**k-1，共（2**k-1）列。
###转移方程：
若j！=0 ：dp[i][j]=dp[i-1][j+1]+dp[i-1][j+2]+dp[i-1][j+3]······ 
也就是说最高位不是0的时候，满足条件的数字个数是，第二高位的数字大于最高位的数字的情况的和。
若j==0：dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+dp[i-1][j+2]+dp[i-1][j+3]······
如果最高位是0，那么第二高位数字则可以取0。也就比上一个情况多加了个dp[i-1][j]。

###最后的结果：
若w%k！=0：结果就是最下面一行的最高位取 0到（2^(w%k)-1)的情况之和。
res=sum(dp[math.ceil(w/k)-1][:2^(w%k)-1])
若w%k==0：最下面一行所有情况都可以使用。
res=sum(dp[math.ceil(w/k)-1][:])

另外题目要求位数>=2,所以需要减去只有一位数的情况（减去2**k）。
```python
import math
while True:
	try:
		k,w=map(int,input().strip().split())
		
		dp = [[0 for j in range(2**k)]for i in range(math.ceil(w/k))]
		for i in range(2**k):
		    dp[0][i] = 1
		for i in range(1,math.ceil(w/k)):#1
		    for j in range(2**k):
		        dp[i][j]=sum(dp[i-1][j+1:])  
		        if j == 0:           #如果最高位是0
		            dp[i][j]+=dp[i-1][j]
		if w%k == 0:
		    res=sum(dp[math.ceil(w/k)-1][:])
		else:
		    res=sum(dp[math.ceil(w/k)-1][:2**(w%k)])

if w/k<=1:     #如果只有一位数，结果就是0
		    res =0
		else:
		    res -=2**k  #减去只有一位数的情况
		print(res)
	except:
		break
```

0.0分

11 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

tym777

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1110: 2^k进制数,动态规划dp解决！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

WU-判定字符位置（C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1050题解（结构体数组与结构体指针的使用）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

tym777

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1110: 2^k进制数,动态规划dp解决！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

WU-判定字符位置 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1050题解（结构体数组与结构体指针的使用）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

WU-判定字符位置（C++代码）