AC代碼

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

題意：

給定一個(gè)數(shù)字序列a1，a2，…，你可以對(duì)這個(gè)序列執(zhí)行幾個(gè)操作。

每個(gè)操作應(yīng)如下所示。您可以選擇一些子序列。

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

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

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

然后數(shù)字4和5是北方，數(shù)字2和6是南方。

之后，您可以執(zhí)行以下操作之一：

所有北方數(shù)字加1，所有南方數(shù)字減1；或

所有南方數(shù)字加1，所有北方數(shù)字減1。

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

然后操作結(jié)束。還要注意，所有的操作都是獨(dú)立的，即當(dāng)一個(gè)操作結(jié)束時(shí)，數(shù)字不再被稱為北方或南方。

現(xiàn)在要使用上述操作將序列的所有數(shù)字轉(zhuǎn)換為零。求最少操作次數(shù)是多少。

題解：

前綴和