PTA 7-5 买地攻略 (25 分)
2023-04-18 12:49:17 时间
题目
数码城市有土地出售。待售的土地被划分成若干块,每一块标有一个价格。这里假设每块土地只有两块相邻的土地,除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价,请你编写程序,根据客户手头的现金量,告诉客户有多少种不同的购买方案。
输入格式: 输入首先在第一行给出两个正整数:N(≤10 4 )为土地分割的块数(于是这些块从 1 到 N 顺次编号);M(≤10 9 )为客户手中的现金量。
随后一行给出 N 个正整数,其中第 i 个数字就是第 i 块土地的标价。
题目保证所有土地的总价不超过 10 9 。
输出格式: 在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。
输入样例:
5 85
38 42 15 24 9
结尾无空行
输出样例:
11
结尾无空行
样例解释:
这 11 种不同的方案为:
38
42
15
24
9
38 42
42 15
42 15 24
15 24
15 24 9
24 9
解题思路
N, maxZijin = map(int, input().split())
inputList = list(map(int, input().split()))
# N, maxZijin = map(int, "5 85".split())
# inputList = list(map(int, "38 42 15 24 9".split()))
ans = []
def dfs(idx:int, cur:int, patch:[int]):
#递归结束
if cur <= 0:
# ans.append(patch[:])
return
elif idx == len(inputList):
return
if cur >= inputList[idx]:
if len(patch) == 0 or idx==(patch[-1]+1):
# print(idx, cur, patch,inputList[idx])
# print(idx, cur, patch)
# and (idx == (patch[-1] + 1))
patch.append(idx)
ans.append(patch[:])
dfs(idx+1, cur - inputList[idx] ,patch)
# return
#消除影响【重要】
patch.pop()
dfs(idx + 1, cur, patch)
dfs(0,maxZijin,[])
print(len(ans))
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击