The title

Digital City has land for sale. The land for sale is divided into lots, each marked with a price. This assumes that each piece of land has only two adjacent pieces of land, except that the two pieces at the beginning and end have only one neighbor. Each customer can purchase multiple contiguous plots of land.

Now given the price of this series of land, please write a program, according to the amount of cash on hand, tell the customer how many different purchase plans.

Input format: Input first gives two positive integers in the first line: N (≤10 4) is the number of blocks divided by land (so these blocks are numbered from 1 to N); M (≤10 9) is the amount of cash in the customer’s hand.

The next line gives N positive integers, where the ith number is the price of the ith piece of land.

They’re guaranteeing that the total value of all the land doesn’t exceed 10, 9.

Output format: Output how many different purchase options the customer has in one line. Please note that the client can only purchase contiguous land.

Example: 5 85 38 42 15 24 9 No blank line at the end Example: 11 No blank line at the end Description: the 11 schemes are as follows: 38 42 15 24 15 24 15 24 24 24 9 9Copy the code

Their thinking

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, Pop () DFS (idx + 1, cur, patch) DFS (0,maxZijin,[]) print(len(ans)Copy the code