https://www.luogu.com.cn/problem/CF1956D

#include <bits/stdc++.h>
using namespace std;
const int maxn = 25;

int n, a[maxn];
vector<pair<int, int>> ans;

void test() {
    putchar('\t');
    for (int i = 1; i <= n; i++)
        printf("%d,", a[i]);
    puts(" !");
}

int mex(int l, int r) {
    set<int> st;
    for (int i = l; i <= r; i++)
        st.insert(a[i]);
    for (int i = 0; ; i++)
        if (!st.count(i))
            return i;
}

// 判断 a[l..r] 全是 0
bool check(int l, int r) {
    for (int i = l; i <= r; i++)
        if (a[i])
            return false;
    return true;
}

// 对 a[l..r] 进行一次操作
void f(int l, int r) {
//    printf("%d %d\n", l, r);
    ans.push_back({l, r});
    int x = mex(l, r);
    for (int i = l; i <= r; i++)
        a[i] = x;
//    test();
}

// 将 a[l..r] 清空为 0
void clean(int l, int r) {
    while (!check(l, r)) {
        f(l, r);
    }
}

void op2(int l, int r, int x);

// 将 a[l..r] 变成 x, 0, 0, .., 0
void op1(int l, int r, int x) {
    if (x == 0) {
        clean(l, r);
        return;
    }
    if (x == 1) {
        clean(l, r);
        f(l, r);
        if (l < r) clean(l+1, r);
        return;
    }
    op2(l, r, x-1);
    f(l, l+x-1);
    clean(l+1, r);
}

// 将 a[l..r] 变成 x, x-1, x-2, .., 2, 1, 0, 0, .., 0
void op2(int l, int r, int x) {
    if (x == 0) {
        clean(l, r);
        return;
    }
    if (x == 1) {
        clean(l, r);
        f(l, r);
        if (l < r) clean(l+1, r);
        return;
    }
    op1(l, r, x);
    op2(l+1, r, x-1);
}

int sum[maxn], tar[maxn][maxn], val[maxn][maxn];
bool vis[maxn][maxn];

int dfs1(int l, int r) {
    if (l > r) return 0;
    if (vis[l][r]) return val[l][r];
    vis[l][r] = true;
    val[l][r] = sum[r] - sum[l-1];
    tar[l][r] = -1;
    int tmp = (r - l + 1) * (r - l + 1);
    if (tmp > val[l][r])
        val[l][r] = tmp, tar[l][r] = r;
    for (int i = l; i < r; i++) {
        tmp = dfs1(l, i) + dfs1(i+1, r);
        if (tmp > val[l][r])
            val[l][r] = tmp, tar[l][r] = i;
    }
    return val[l][r];
}

void dfs2(int l, int r) {
    if (tar[l][r] == -1)
        return;
    if (tar[l][r] == r) {
        op2(l, r, r-l);
        f(l, r);
        return;
    }
    dfs2(l, tar[l][r]);
    dfs2(tar[l][r]+1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a+i), sum[i] = sum[i-1] + a[i];
    dfs1(1, n);
    dfs2(1, n);
    printf("%d %d\n", dfs1(1, n), (int)ans.size());
    for (auto pi : ans)
        printf("%d %d\n", pi.first, pi.second);
    return 0;
}