• 在藍橋杯當中，對于回溯是屬于一個必考的問題，但是除了回溯的幾個基本的問題，如果通過剪枝來提前刪去無效的分支，以大大減少時間復雜度是需要我們進一步思考的問題！
• 回溯的基本問題：
  • 回溯的初始狀態
  • 回溯的狀態轉移
  • 回溯的結束狀態
• 其中，這個剪枝的考點就可以在結束狀態部分進行充分的考察
• 那么這個剪枝有哪些思路與思考？
  • 對于這個n個物體，求和的回溯問題：可以考慮使用前綴和，排序兩個手段進行提前剪枝(以真題買瓜進行深入的分析)

買瓜

買瓜

• 首先按照正常的回溯的思路：

  • 首先考慮在回溯的過程中，我們需要記錄什么參數？
    • 由于要更新這個最終的切西瓜的刀數，所以得設置一個變量記錄當前的切西瓜的刀數
    • 那么當前是切的哪一個西瓜？所以還得記錄一下這個所處理的西瓜的下標
    • 那么怎么知道當前的得到的西瓜的重量？所以還得設置一個變量去記錄當前所得到的西瓜
  • 總的來說，回溯的過程中，需要三個變量(i, k, cursum),分別表示當前處理到的西瓜的下標，當前已經切的西瓜刀數，當前得到的西瓜的重量

• 考慮這個結束的狀態與更新答案的狀態

  • 結束的狀態：當處理到的西瓜的下標達到n的時候，就返回(因為西瓜的下標是從0開始的，所以當處理到的西瓜的下標到達n就說明已經處理完了)
  • 更新的狀態：當當前的重量等于目標重量的時候，就比較當前的切西瓜的次數與當前的切西瓜的最優次數，進行一個更新

• 由于有除以2的操作，所以我們可以將這個目標都擴大兩倍，同時將這個西瓜重量也擴大兩倍，這樣就不用除以2

# 對于每個西瓜，可以選擇切與不切
n, m = map(int, input().split())
m = m<<1 
num = list(map(int, input().split()))
a = [i*2 for i in num]
ans = n+1
# 當前的瓜的下標，當前切的刀數，當前的重量
def dfs(i, k, cursum):global ansif cursum == m:ans = min(ans, k)if i == n:return# 不選dfs(i + 1, k, cursum)# 選擇，如果當前的cursum 沒有超過這個mif cursum + num[i] > m:return# 選擇一整個西瓜dfs(i + 1, k, cursum + a[i])# 選擇半個西瓜dfs(i + 1, k + 1, cursum + num[i])
dfs(0,0,0)
print(ans if ans != n+1 else -1)

• 思考：剪枝不夠充分，目前的剪枝是有對結束狀態的判斷，那么還有什么情況可以考慮？
  • 考慮及時加上全部的西瓜仍然<m,這個時候就沒有必要遞歸下去了，直接結束(難道我們每次都得使用這個sum函數進行求解嗎？當然不是，我們可以使用前綴和進行求解，但是為了方便起見，得將原始的數組和前綴和數組進行轉置)
  • 如果當前的重量已經超過了這個 m就沒有必要繼續遞歸下去了

# 總的來說，m,n是輸入
n,m = map(int,input().split())
m = m << 1
num = list(map(int,input().split()))
num.sort()
a = [i<<1 for i in num]
pre = [0]*n
pre[0] = a[0]
for i in range(1,n):pre[i] = pre[i-1] + a[i]
a = a[::-1]
pre = pre[::-1]
ans = n+1
def dfs(i,k,cursum):global ansif cursum == m :ans = min(ans,k)# if k >= ans:#     returnif i == n or cursum >= m or cursum + pre[i] < m:returndfs(i+1,k,cursum )dfs(i+1,k+1,cursum + a[i] // 2)dfs(i+1,k,cursum + a[i])dfs(0,0,0)
print(ans if ans != n+1 else -1)

最大數字

最大數字

• 錯誤的遞歸思路：每次只要么處理一位操作1要么處理操作2，這樣的處理思路是有問題的，你要么在位數i的時候，直接用完對應的操作1或者操作2，使其變為9,如果不能變為9，那么就盡可能大(操作2是有可能剩余的，但是操作1是不可能剩余的)
• 包含一點貪心的思路

import os
import sys# 請在此輸入您的代碼# 肯定是按照這個數位進行操作的
N,A,B = map(int,input().split())
N = list(str(N))
n = len(N)
# 需要記錄什么？操作1的次數，操作2的次數，當前操作的是哪一位？
ans = 0
def dfs(i,n1,n2,curnum):global ansif i == n:ans = max(ans,curnum)return # 先進行加法，看看能不能將該位變為9num = int(N[i])ad = min(n1,9-num)n1 -= ad dfs(i+1,n1,n2,curnum*10 + num + ad)n1 += ad # 進行減法if n2 > num:n2 = n2 - (num + 1)dfs(i+1,n1,n2,curnum*10 + 9)n2 = n2 + (num + 1)
dfs(0,A,B,0)
print(ans)