題意

有一個人在玩一個離子激活的游戲，題目的背景是模擬的化學當中的離子能量躍遷。在化學當中，離子吸收能量可以從低能態(tài)躍遷到高能態(tài)，并且放出一定的能量。
現在有N粒離子排成一排（下標1-N），每一個離子都有自己的能量參數。也就是吸收多少能量可以躍遷，并且躍遷之后會放出多少能量。還有一個特殊的性質就是這些離子之間帶有連帶關系，默認的連帶關系是第i個離子與第i+1個離子連帶。當i離子躍遷的時候，即使i+1的離子沒有吸收能量也會發(fā)生躍遷。其中第N個離子無法建立連帶關系。
現在這個人獲得了K次改變離子之間連帶關系的能力，它必須要嚴格改變K個離子的連帶對象。除此之外我們可以自由選擇任意個離子進行激活，請問我們最多能夠獲得多少能量收益？能量收益是指獲得的能量減去消耗的能量。

樣例

在樣例當中我們將5離子的紐帶改變成1離子，激活離子5，這樣我們一共可以讓1-5離子都進行躍遷。所帶來的的能量收益就是5 + 6 + 7 + 8 + 10 - 1 = 35

題解

拿到手沒什么思路，我們可以先從簡單的情況開始思考。
K=0

我們分析完了K=0最簡單的情況之后，發(fā)現了一件事，就是除了我們改變連帶的離子之外，其他的離子都是連續(xù)的。我們激活一個可以激活一串，這有點像是什么呢，像是鏈表，我們改變離子的連帶關系，其實就是修改鏈表當中某一個節(jié)點的next指針。

比如我們看這張圖，當離子a的連帶對象從a+1修改成b之后，其實意味著我們將a節(jié)點的next指向了b。這樣當我們遍歷的時候，a的下一個位置就是b。
a的next位置是任意的，可以在a的前面也可以在a的后面，但是不能是a本身。想明白了這點之后，其實所謂的修改K個離子的連帶關系，就是在鏈表當中修改K條邊。然后我們可以選擇若干個起始位置來遍歷鏈表，使得題意規(guī)定的收益最大。
另外我們發(fā)現不論這K條邊連接如何，除了這K條邊之外的內容都還是順序連接的。我們可以使用前綴和算法來快速求某一段區(qū)間的和。

前綴和算法

并且我們要維護presum也非常簡單，其中presum[1] = A[1]，對于i > 1的所有i，都有presum[i]=presum[i-1] + A[i]。通過這么一個簡單的遞推式，我們就可以非常方便地求出所有的presum，計算所有的前綴和了。
前綴和非常方便，在很多題目當中都有使用，但是有一個小小的條件就是維護區(qū)間和的數組內的元素不能發(fā)生變化。否則的話就沒辦法使用了。

K >= 2

講完了前綴和之后我們繼續(xù)來分析問題，我們接著看下K >= 2時的情況。我們可以發(fā)現當K > 2時，我們只要激活一個小于N的i，就可以獲得全部離子。
我們來看一個例子，這是K=2時的情況：

我們激活的是某一個i，然后在a位置跳轉到了1，又在i-1跳轉到了a+1。雖然我們跳轉了兩次，但是所有的離子都沒有浪費。
我們利用遞推的思想可以發(fā)現，只要K >= 2，就可以保證將所有的離子都納入囊中。所以我們很容易發(fā)現，我們只需要選擇代價最小的i就行了。

K = 1

為什么把K=1的情況放到最后呢？因為它最復雜，情況很多，非常非常容易遺漏。
我們前面曾經提到過，對于i位置而言，它的連帶對象可以在它前面也可以在它后面。我們針對這兩種情況需要單獨分析，首先是它的連帶對象在它前面。那么最優(yōu)的情況一定是它和1號離子連帶。這樣的話，我們只要激活[2, i]區(qū)間里任何一個離子，都可以獲得前i個離子的總收益。但是這里又有一個問題，我們要不要再激活離子i+1呢？如果激活的話，我們就獲得所有離子的收益，也可以不激活。

我們看完了連帶的節(jié)點在前面的情況再來看看連帶的情況在后面會怎么樣，還是看這張圖：

我們可以看到a點的連帶在其后的b點，這時候我們也有兩種情況，第一種情況是只激活1，這樣的話，我們可以拿到除了[a+1, b-1]區(qū)間內的值。第二種情況是激活1之后再激活a+1，這樣我們也可以獲得全部的離子，但是需要花費A[1]和A[a+1]。
這只是表面的分析，當我們深入分析之后會發(fā)現，由于離子釋放的能量一定是正數。我們當然希望它跳過的區(qū)間越小越好，因為跳過得多了都是損失。最極端的情況應該是b=a+2，也就是說我們只跳過a+1這一個元素。跳過a+1這個元素有兩種情況，第一種是真跳，也就是說拋棄了這個取值，第二種情況是假跳，我們雖然跳過了，但是還是會人為將它激活。

是的，你沒有看錯，這道題一共有7種情況，少了隨便哪一種都沒有辦法AC。題目雖然簡單，但是我們在做題的時候想要一下子把這7中情況都想明白理清楚實在是不容易，不過這樣的題目才更加值得我們去做，因為真的很鍛煉思維，對于提升我們思維的縝密程度非常有幫助。
最后，我們附上代碼。

import sys n, k = list(map(int, input().split(' ')))activate = list(map(int, input().split(' '))) deactivate = list(map(int, input().split(' ')))presum = [0 for _ in range(n+2)]for i in range(1, n+1):presum[i] = presum[i-1] + activate[i-1]ret = 0if k == 0:for i in range(1, n+1):# 情況0，不需要考慮連帶ret = max(ret, presum[n] - presum[i-1] - deactivate[i-1]) elif k == 1:for i in range(1, n):# 情況3 n-1連1ret = max(ret, presum[n-1] - deactivate[i-1])# 情況3再加上第N個離子if deactivate[n-1] < activate[n-1]:ret += (activate[n-1] - deactivate[n-1])deac = sorted(deactivate[1:n-1])ac = sorted(activate[1:n-1])# 情況5，激活1，跳過1個節(jié)點ret = max(ret, presum[n] - deactivate[0] - ac[0])# 情況6 激活1，跳過1個節(jié)點后，再激活ret = max(ret, presum[n] - deactivate[0] - deac[0])# 情況4 ret = max(ret, presum[n] - deac[0] - deac[1])# 情況7 1連n，激活ifor i in range(2, n+1):ret = max(ret, presum[n] - presum[i-1] - deactivate[i-1]) else:# 情況1for i in range(1, n):ret = max(ret, presum[n] - deactivate[i-1]) # 情況2ret = max(ret, activate[n-1] - deactivate[n-1])print(ret)

這道題有點燒腦，光憑我說可能很難完全理解清楚，建議大家多拿紙筆出來畫一畫，會有助于思考。

總結

以上是生活随笔為你收集整理的牛客网-数据结构笔试题目（八）-离子能力跃迁问题求解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。