PTA 7-5 买地攻略 (25 分)

题目

数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。

现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。

输入格式：
输入首先在第一行给出两个正整数：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))