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。

然后操作结束。还要注意，所有的操作都是独立的，即当一个操作结束时，数字不再被称为北方或南方。

现在要使用上述操作将序列的所有数字转换为零。求最少操作次数是多少。

题解：

前缀和