給定：N、K、M和A（陣列）
N =陣列中的元素數
K = 答案中可以避免/不考慮的最大連續陣列元素
|A| = N
從陣列的最后一個索引開始，您必須找到使用陣列元素可以獲得的最大總和，以便在任何時刻總和都不會被M整除。的總和可以通過從最后一個索引遍歷到陣列（第一索引來獲得性，以便），并且有選擇地要么包括該元素到最終的答案，或避免它。
有兩個條件：
- 當一個專案包含d 時，直到那一刻為止包含的所有元素的總和（包括正在包含的當前元素）不應被 M 整除。
- 當一個專案被避免時，必須記住你一次最多可以避免 K 個連續的陣列元素。
注意：嚴格要求從最后一個索引開始，跳過任何索引都將計入可以避免的最大連續元素的限制（即 K）。
如果無法通過在遍歷的所有實體中滿足兩個條件來從最后一個索引遍歷到第一個索引，則我們必須回傳-1，否則回傳可能的最大總和。
約束：
2 <= N <= 10^5
1 <= K <= 10
1 <= M <= 20
示例 1：
N = 5
K = 1
M = 2
A = [1, 2, 3 ,4, 5]
Output : 5 4 2 = 11
示例 2：
N = 5
K = 2
M = 2
A = [3, 4, 2, 6, 8]
Output = -1
示例 3：
N = 7
K = 2
M = 2
A = [1,4,2,6,3,7,7]
Output : 7 6 2 4 = 19
uj5u.com熱心網友回復：
我們可以做 3-D 動態規劃來解決這個問題，與另一篇文章非常相似。這是我正在使用的公式的定義：
Let dp[i][k][r], 0 <= i < N, 0 <= k <= K, 0 <= r < M
be the maximum valid sum achievable after processing indices [i, i 1, ..., N-1]
such that index i is our kth consecutive skip and the sum's remainder is r (mod M).
We want max(dp[0][_][_])
dp[i][k][r] = -INF if k i > N
= -INF if r == 0 and k i /= N
= -INF if r /= 0 and k i == N
= 0 if r == 0 and k i == N
= dp[i 1][k-1][r] if k > 0 and r /= 0
= A[i] max(dp[i 1][j][(r-A[i]) % M] over all j), if k == 0
該公式很長，因為允許0（技術上可被 整除M）的初始空和，但所有其他的都不允許。上面未包含的公式還有一個初始值：如果A[N-1]（最后一個元素）不能被 整除M，則dp[N-1][0][A[N-1]%M]是A[N-1]。您可以將這個公式縮短兩行，但您至少需要匹配 4 個不同的模式。
時間和空間復雜度為O(NMK)，但空間復雜度可以O(MK)通過只存盤 DP 表的最后兩行來降低。
這是該 DP 公式的 Python 計算：
def f(A: List[int], N: int, K: int, M: int) -> int:
assert N == len(A)
if M == 1:
return -1
dp = [[[-math.inf for _ in range(M)] for _ in range(K 1)] for _ in range(N)]
for i in range(N):
k = N - i
if 0 <= k <= K:
dp[i][k][0] = 0
if A[N - 1] % M != 0:
dp[N - 1][0][A[N - 1] % M] = A[N - 1]
for i in reversed(range(N - 1)):
elem = A[i]
# When k == 0
for r in range(1, M):
for j in range(K 1):
dp[i][0][r] = max(dp[i][0][r], elem dp[i 1][j][(r - elem) % M])
# When k > 0
for k in range(1, K 1):
for r in range(1, M):
dp[i][k][r] = dp[i 1][k - 1][r]
ans = max([max(x) for x in dp[0]])
return ans if math.isfinite(ans) else -1
如果你想測驗這個代碼和其他答案，加上一個緩慢的蠻力解決方案，這里是一個在線代碼運行器
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/312887.html
上一篇：當我在Python和NumPy中取第n個根時，我實際上得到了n個現有根中的哪一個？
下一篇：廣義關聯勒讓德多項式