給定一個陣列A，您可以重復洗掉其k總和為 的任何連續子陣列tar。A通過這個程序輸出是否可以清空。
A是整數陣列，k是正整數，tar是整數。
例如，A=[1,2,3,4];k=2;tar=5
然后您可以洗掉[2,3]fromA使其變為[1,4]. 然后你[1,4]從A; 中洗掉 它變成空的。因此，演算法應該輸出True。
目前我找到了一個O(n^2/k*comb(n/k,k))演算法。有沒有更好的？
我的演算法
首先使用dp，查找是否A[i:j]可以為空，然后列舉最后洗掉的子陣列的所有元素，及時O(comb((j-i)/k, k))，
python3的示例代碼，時間k是3：
from functools import lru_cache
from itertools import accumulate
def solve(A, k, tar):
# only works when k = 3
assert k==3
presum = list(accumulate(A, initial=0))
@lru_cache(None)
def judge(i, j):
"""
find if s[i:j] can be full erased
"""
l,remainder = divmod(j-i,k)
if remainder != 0 or presum[j]-presum[i] != tar*l:
return False
if l<=1:
return True
# enumerate the last 3 elements to be erased
# # find triplets that sum to tar
for a1 in range(i, j, 3):
for a2 in range(a1 1, j, 3):
for a3 in range(a2 1, j, 3):
if A[a1] A[a2] A[a3]==tar:
prv = i
flag = True
for nxt in a1,a2,a3,j:
if not judge(prv, nxt):
flag = False
break
prv = nxt 1
if flag == True:
return True
return False
return judge(0,len(A))
print(solve([1,2,3,4,8,0],3,9))
附加問題
我也想知道當kis3和時是否有任何特定的演算法2。
k=3貪婪時不起作用的測驗用例：
A=[5,5,5,1,9,7,3,0,10, 5,5,5, 10,0,3,7,9,1,5,5,5];tar=15;k=3
uj5u.com熱心網友回復：
對于我們處理一系列操作的問題，您通常可以通過引數化您將執行的第一個或最后一個操作來獲得動態規劃解決方案。
對于我們的陣列A = [a_0, a_1, ... a_{n-1}]，讓我們猜猜最后一步是什么。必須洗掉k與 our 相加的元素target，這些元素[x_0, x_1, ... x_{k-1}]形成 A 的子序列，該子序列將 的其他元素A劃分為最多k 1其他子陣列。在執行最后一個操作之前，其他子陣列已經被一些操作完全單獨洗掉，每個子陣列上的子問題完全類似于我們原來的問題。這是一個最優子結構的例子。
既然框架已經搭建好了，我們來說一下細節。有很多簡單的邊緣情況：如果k是 1，或者如果陣列的長度不能被 整除k，或者如果陣列的總和不正確，我們應該首先檢查。我還將假設target和 的條目A是非負的，但這可以通過對代碼的少量添加進行修改，而不會影響運行時的復雜性。
我們的子問題需要跟蹤哪些變數？有我們當前陣列的左右邊界，以及我們已經采用的所有外部磁區元素的數量和總和。我們還不知道哪些k磁區元素將出現在最后一次操作中——它們可能分布在整個原始陣列中。
我們將從左到右遍歷陣列，在每個點測驗我們是否可以將當前元素用于該外部磁區，或者是否將下一個 k、2k、或 3k、...元素一起作為一個連續子陣列，然后繼續。我們可以從考慮中過濾掉大多數子陣列：如果子陣列 S 的長度是 k, 的倍數m*k，并且它的總和是 ，那么它是潛在可解的m*target。我們可以使用前綴和來快速測驗。
Python
def solve(arr: List[int], k: int, target: int) -> bool:
"""Decide whether arr is completely removable
Given an array of nonnegative integers arr, a positive integer length k,
and a nonnegative target sum, decide whether we can remove all elements
of arr by repeatedly removing k consecutive elements summing to target.
"""
assert k > 0
assert target >= 0
# This section deals with any easy edge cases
if len(arr) % k != 0:
return False
if k == 1:
return all(x == target for x in arr)
prefixes = list(itertools.accumulate(arr, initial=0))
if target == 0: # Assumes target >= 0 and all values >= 0
return prefixes[-1] == 0
if prefixes[-1] != target * (len(arr) // k):
return False
if k == len(arr):
return True
reverse_index = collections.defaultdict(list)
starts_to_ends = collections.defaultdict(list) # Candidate subarrays
for right, x in enumerate(prefixes):
remainder = x % target
for left in reverse_index[remainder]:
if (right - left) % k == 0:
if (right - left) // k == (x - prefixes[left]) // target: # Valid sum
starts_to_ends[left].append(right-1)
reverse_index[remainder].append(right)
@functools.lru_cache(None)
def can_solve(left: int, right, outer_need: int, outer_sum_need: int) -> bool:
elements_remaining = right - left 1
# We've reached the end of our array
if elements_remaining == 0:
return outer_need == outer_sum_need == 0
# All elements must go to the outer partition
if elements_remaining == outer_need:
return prefixes[right 1] - prefixes[left] == outer_sum_need
# We've used k elements for the outer partition, but
# their sum is too small
if outer_need == 0 and outer_sum_need != 0:
return False
# Test whether we can split into two subproblems
for poss_ending in starts_to_ends[left]:
if poss_ending >= right:
break
if (can_solve(left, poss_ending, 0, 0)
and can_solve(poss_ending 1, right, outer_need, outer_sum_need)):
return True
# We are just starting a subproblem: Initialize outer partition as empty
# and try using current element in outer partition
if outer_need == 0 and outer_sum_need == 0:
if (arr[left] <= target
and can_solve(left 1, right, k - 1, target - arr[left])):
return True
# Try using current element in outer partition
if outer_need > 0 and arr[left] <= outer_sum_need:
if can_solve(left 1, right, outer_need - 1, outer_sum_need - arr[left]):
return True
return False
return can_solve(left=0, right=len(arr) - 1, outer_need=0, outer_sum_need=0)
這可以修改為實際輸出要按順序洗掉的陣列，還有一些作業。當前運行時間是O(n^2 * target * n/k)（由于我們的預過濾技巧，當陣列的總和或長度錯誤時，可以節省 k 的因子）。對于許多可解陣列，“貪婪”策略將起作用并且速度更快，因此優化可能是首先嘗試。
我相信（并有一些經驗證據）O(n^2 * target)通過消除遞回函式內部的回圈，可以將運行時降低到。與其將下一個k, or 2k, 或3k元素的所有“塊”作為單獨的子問題進行測驗，似乎您只需要測驗總和有效的最大塊，盡管我還沒有找到令人滿意的證明這總是給出正確的答案。
uj5u.com熱心網友回復：
擴展我的評論：k = 2 可以通過線性時間貪婪演算法處理（將 A 的每個元素推入堆疊，只要它們存在就彈出頂部的兩個元素并求和到 tar）。
k = 2 的不同之處在于，如果 A 包含 x, y, z 且 x y = tar 和 y z = tar，那么 x = z 并且我們用 y 洗掉哪一個都無關緊要。
更正式地，我們通過對 A 長度的歸納表明，沒有移除會導致我們失去清空陣列的能力。這在 A 為空時很明顯。歸納地，假設所有比 A 短的可以被清空的陣列都可以被任何最大的有效洗掉序列清空。如果 A 不能被清空，那么就沒有什么可失去的了。否則，我們可以洗掉一些對 p 并繼續清空 A。假設我們洗掉了一些其他對 q。有兩種情況。
p 和 q 重疊。正如我們上面所討論的，結果陣列將是相同的，并且假設我們可以清空它。
p 和 q 不重疊。然后我們可以通過洗掉 p 然后 q 或 q 然后 p 來獲得相同的陣列。通過假設和歸納假設，前一個順序必須允許我們清空結果陣列，所以后一個順序也可以。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/346256.html
標籤：算法