题解：CF2003E1 Turtle and Inversions (Easy Version)

Identity_Equation · 2025-11-17 19:43:21 · 题解

细节有点多，建议多画画图。

首先我把这个排列的数字分为两个不同的集合:一个中数字大于我定义的的一个数字 p，另一个则是剩下部分。我记前者为 A，后者为 B。

对于一个 l_i，r_i 区间，前面的 (l_i, k_i) 部分从 B 中取，(k_i+1,r_i) 部分从 A 中取。

显然对于这两个部分都应该为降序的才更加优。

然后是不包括在任何区间的部分，很明显降序填最为优秀。

包括与否的做法相差不大，都是找一个分界，包括部分的前面填 B，后面填 A。不包括部分前面填 A，后面填 B。

然后就是一个背包，我的建议是多画图来理解。我来以包括部分为例。

考虑重定义 k_i 为选了多少个 B，L_i 为 i 区间的长度。

那么这个区间贡献逆序对数量为:

前面两项是 B 的部分的贡献，后面是 A 的贡献。

后半部分建议读者自己推。

#include <bits/stdc++.h>
#define int long long 

using namespace std;
const int N = 5e3 + 5;
int l[N], r[N], f[2][N];
const int inf = 1e15;
signed main() {
    // freopen("ex_range2.in", "r", stdin);
    // freopen("range.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T --) {
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        int n, m; cin >> n >> m;
        l[0] = r[0] = 0, l[m + 1] = r[m + 1] = n + 1;
        for (int i = 1 ; i <= m ; i ++)
            cin >> l[i] >> r[i];
        int L = 0; bool u = 0;
        for (int i = 0 ; i <= n ; i ++)
            f[0][i] = f[1][i] = -inf;
        // memset(f, 0, sizeof(f));
        f[u ^ 1][0] = 0;
        for (int i = 1 ; i <= m ; i ++) {
            L = l[i] - r[i - 1] - 1;
            if (L) {
                for (int j = 0 ; j <= n ; j ++) {
                    f[u][j] = -inf;
                    for (int k = 0 ; k <= min(j, L) ; k ++) {
                        // if (f[u ^ 1][j - k] == 0) continue;
                        f[u][j] = max(f[u][j], 
                            f[u ^ 1][j - k] + 
                            (r[i - 1] - j + k) * (L - k) + (L - k) * (L - k - 1) / 2 +
                            (l[i] - 1 - k) * k + k * (k - 1) / 2
                        ); 
                    }
                }                
                // cout << "A" << i << '\n';
                // for (int j = 1 ; j <= n ; j ++) cout << f[u][j] << ' ';
                // cout  << '\n'; 
                u = u ^ 1;

            } 
            L = r[i] - l[i] + 1;
            for (int j = r[i] - i ; j >= 0 ; j --)  {
                f[u][j] = -inf;
                for (int k = 1 ; k <= min(j, L - 1) ; k ++) {
                    // if (f[u ^ 1][j - k] == 0) continue;
                    f[u][j] = max(f[u][j],
                        f[u ^ 1][j - k] + 
                        (l[i] - 1) * k + (k - 1) * k / 2 +
                        (L - k) * (l[i] - 1 - j + k) + (L - k) * (L - k - 1) / 2
                    );
                }
            }
            // cout << 'B' << i << '\n';
            // for (int j = 1 ; j <= n ; j ++) cout << f[u][j] << ' ';
            // cout << '\n';
            u = u ^ 1;
        }
        int Ans = -inf;
        // cout << f[u ^ 1][4] << '\n';
        for (int i = m ; i <= n - m ; i ++) {
            int L = n - r[m];
            if (L == 0) Ans = max(Ans, f[u ^ 1][i]);
            else {
                int A = f[u ^ 1][i] + L * r[m] + (L - 1) * L / 2; 
                Ans = max(Ans, A);
            }
        }
        cout << Ans << '\n';
    }
    return 0;
}
/*
8 2
1 3
5 8

21 

22
*/

注意 f 要设为 inf。比赛就因为这个挂成 30 了。