PTA 7-5 买地攻略 (25 分)
PTA 7-5 买地攻略 (25 分)
freesan44
发布于 2021-12-06 19:32:55
发布于 2021-12-06 19:32:55
题目
数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。
输入格式： 输入首先在第一行给出两个正整数：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))本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021/11/18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录