AC代碼

https://codeforces.com/contest/1775/submission/189892616

題意：

給定一個數字序列a1，a2，…，你可以對這個序列執行幾個操作。

每個操作應如下所示。您可以選擇一些子序列。

(相關資料圖)

然后你把這個子序列中奇數位置的所有數字稱為北方，把這個子順序中偶數位置的所有數值稱為南方。

在這種情況下，只考慮數字在子序列中的位置，而不是在原始序列中。

例如，考慮序列1,4,2,8,5,7,3,6,9及其子序列4,2,5,6。

然后數字4和5是北方，數字2和6是南方。

之后，您可以執行以下操作之一：

所有北方數字加1，所有南方數字減1；或

所有南方數字加1，所有北方數字減1。

因此，從序列4,2,5,6中， 則可以得到 5、1、6、 5或3、3、4、7。

然后操作結束。還要注意，所有的操作都是獨立的，即當一個操作結束時，數字不再被稱為北方或南方。

現在要使用上述操作將序列的所有數字轉換為零。求最少操作次數是多少。

題解：

前綴和

標簽： HTTPS