集邮比赛2/Collecting Stamps2题解

题目分析：

想让子序列JOI的数量最大化，我们就需要分析插入不同字符对结果的影响。

解题思路：

1. ‌计算原始JOI数量‌：对于每个O前面 J的数量和后面I的数量相乘，就是这个O所贡献的JOI的数量，然后累加每个O的贡献，就是原始JOI的数量。

2. ‌考虑插入不同字符的影响‌：

• 插入J：会增加它后面的所有O的前缀J的数量，因此可以放在最前面，使增加数最大。

• 插入O：会增加前面所有J和后面所有I的组合，因此需要讨论每个位置。

• 插入I：会增加它前面所有的O的后缀I计数，因此最优解是放在最后。

高效计算‌：我们可以先预处理每个位置的前缀J计数和后缀I计数，以便快速计算插入不同字符带来的增量。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    string s;
    cin>>n>>s;
  
    // 预处理前缀J和后缀I的数量
    vector<int> J(n+1, 0); // J[i]表示前i个字符中J的数量
    vector<int> I(n+1, 0);  // I[i]表示从i开始到末尾的I的数量

    // 计算原始JOI数量
    for(int i=0; i<n;i++){
        J[i+1] = J[i] + (s[i] == 'J');
    }
    for(int i=n-1; i>=0;i--){
        I[i] = I[i+1] + (s[i] == 'I');
    }

    long long ans = 0;
    for (int i=0; i<n;i++) {
        if (s[i] == 'O') {
            ans += (long long)J[i] * I[i+1];
        }
    }
    
    // 计算插入每个位置能带来的最大增量
    long long zl = 0;
    
    // 尝试在每个位置插入J/O/I
    for (int p=0;p<=n;p++){

        // 插入J的情况：会增加后面所有O的J计数
        long long incJ = 0;
        for (int i=p;i<n;i++) {
            if (s[i] == 'O') {
                incJ += suffixI[i+1];
            }
        }

        // 插入O的情况：会增加前面所有J和后面所有I的组合
        long long incO = (long long)J[p] * I[p];

        // 插入I的情况：会增加前面所有O的I计数
        long long incI = 0;
        for (int i=0;i<p;i++) {
            if (s[i] == 'O') {
                incI += J[i];
            }
        }

        // 取三种插入情况的最大增量
        long long cm = max(max(incJ, incO), incI);
        if(cm > zl) {
            zl = cm;
        }
    }
    cout<<ans + max_increase<<endl;
    
    return 0;
}

时间复杂度： $O(n^2)$。

对于 $n=1 \times 10^5$ 以上的数据会超时，因此我们需要优化。

优化

1. 预处理每个位置前面O的数量和后面O的数量。
2. 预处理每个位置前面J的数量和后面I的数量。
3. 计算插入J/O/I的增量时可以基于预处理的数据快速计算。

优化后的代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s;
    cin>>n>>s;
    
    // 预处理前缀J和后缀I的数量
    vector<int> J(n+1, 0);
    vector<int> I(n+1, 0);
    
    for (int i=0; i<n;i++) {
        J[i+1] = J[i] + (s[i] == 'J');
    }
    
    for (int i=n-1; i>=0;i--) {
        I[i] = I[i+1] + (s[i] == 'I');
    }

    // 预处理前缀O的J计数和后缀O的I计数
    vector<long long> qz(n+1, 0); // 前i个字符中所有O前面J的总和
    vector<long long> hz(n+1, 0); // 从i开始所有O后面I的总和
    
    for(int i=0;i<n;i++) {
        qz[i+1] = qz[i];
        if (s[i] == 'O') {
            qz[i+1] +=J[i];
        }
    }
    
    for (int i=n-1; i>=0;i--) {
        hz[i] = hz[i+1];
        if(s[i] == 'O') {
            hz[i] += I[i+1];
        }
    }
    
    // 计算原始JOI数量
    long long ans = 0;
    for (int i=0;i<n;i++) {
        if (s[i] == 'O') {
            ans += (long long)J[i] * I[i+1];
        }
    }
    
    // 计算插入每个位置能带来的最大增量
    long long zl = 0;
    
    for (int pos = 0; pos <= n; ++pos) {
        // 插入J的情况：会增加后面所有O的J计数
        long long incJ = hz[pos];
        
        // 插入O的情况：会增加前面所有J和后面所有I的组合
        long long incO = (long long)J[pos] * I[pos];
        
        // 插入I的情况：会增加前面所有O的I计数
        long long incI = qz[pos];
        
        // 取三种插入情况的最大增量
        long long cm = max(max(incJ, incO), incI);
        if (cm > zl) {
            zl = cm;
        }
    }
    
    cout<<ans + cm<<endl;
    
    return 0;
}

优化后的时间复杂度：$O(n)$。

现在可以处理 $1 \times 10^5$ 以上规模的数据。主要优化点在于预处理了qz和hz数组，使得计算增量时可以 $O(1)$ 时间完成。