CF2169C

Problem - C - Codeforces

这题有2个解法，然而我赛时一个没写出来，这不是废物是什么？

解法一

对于任意区间 [L,R]：

$$\Delta = (R-L+1)(L+R) - (pre[R]-pre[L-1])$$

换算一下，得到：

$$\Delta =(R^2+R−pre[R])+(pre[L−1]−(L^2−L))$$

注意到

$$\Delta = \underbrace{(R^2+R−pre[R])}_{只与R有关}+\underbrace{(pre[L−1]−(L^2−L)) }_{只与L有关}$$

求$\Delta$的最大值即可

怎么没写出来呢？

#include <bits/stdc++.h>
using namespace std;

const int N = 1e9 + 5;

void solve(){

    int n;
    cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    int mx1 = 0, mx2 = 0;
    for (int i = 1; i <= n; ++i) {
        int x = pre[i - 1] - i * (i - 1);
        mx1 = max(x, mx1);
        x = i * (i + 1) - pre[i];
        mx2 = max(x, mx2);
    }

    cout << pre[n] + mx1 + mx2 << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

这是错的，因为L要小于R，而我取了全局最大：

int mx1 = 0, mx2 = 0;
for (int i = 1; i <= n; ++i) {
    int x = pre[i - 1] - i * (i - 1);
    mx1 = max(x, mx1);
    x = i * (i + 1) - pre[i];
    mx2 = max(x, mx2);
}

正解是：

int mx = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
    int x = pre[i - 1] - i * (i - 1);
    mx = max(x, mx);
    x = i * (i + 1) - pre[i] + mx;
    ans = max(x, ans);
}

这样可以保证L<=R

妙啊

AC码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e9 + 5;

void solve(){

    int n;
    cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    int mx = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x = pre[i - 1] - i * (i - 1);
        mx = max(x, mx);
        x = i * (i + 1) - pre[i] + mx;
        ans = max(x, ans);
    }

    cout << pre[n] + ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

解法二

对于任意区间 [L,R]：

原区间和为：

$$\displaystyle\sum_{i=L}^{R} a_i$$

替换后的区间和：

$$T = (R-L+1)(L+R)$$

神奇的来了，注意到

$$T = (R-L+1)(L+R) = 2 \times \dfrac{(R-L+1)(L+R)}{2}$$

这是什么？

$$\dfrac{(R-L+1)(L+R)}{2}$$

这是等差序列的求和公式！：

$$S_n = \dfrac{{项数}\times (\text{首项} + \text{末项})}{2}$$

所以：

$$T = 2 \times \dfrac{(R-L+1)(L+R)}{2} =2 \times (L+(L+1)+⋯+R)$$

所以$T$也可以写成:

$$\displaystyle{2 \times \sum_{i=L}^{R}} i = \displaystyle{ \sum_{i=L}^{R}} 2i$$

所以$\Delta$可以写成:

$$\displaystyle{\Delta = T - \displaystyle\sum_{i=L}^{R} a_i = \sum_{i=L}^{R} {(2i - a_i)}}$$

于是问题简化成：

寻找区间，使得 $\displaystyle{\Delta = \sum_{i=L}^{R} {(2i - a_i)}}$ 最大

这已经是标准最大子段和问题了

AC码如下：

#include<bits/stdc++.h>
using namespace std;
    
const int N=1e9+5;
    
void solve(){
    
    int n; cin >> n;
    vector<int> a(n + 1), b(n + 1); 
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
        b[i] = 2 * i - a[i];
    }
    
    long long ans = 0, tot = 0;
    for (int i = 1; i <= n; ++i) {
        tot = max(0LL, tot + b[i]);
        ans = max(tot, ans);
    }

    cout << ans + sum << endl;

}
    
int main(){
    
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)
    solve();
    return 0;
    
}