排列重排与权值最大化：动态规划解题报告

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, mod = 998244353;
int n, a[N], b[N], dp[N][N], ans, cnt;
int f[N], g[N], sum[N], tmp[N];
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
inline void upd(int &x, int y) { x = (x + y) % mod; }
int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) b[i] = read();
    for (int i = 1; i <= n; ++i) {
        int mx = -1;
        for (int j = 1; j <= n; ++j) {
            if (a[j] > mx) upd(dp[i][j], dp[i][j - 1] + 1);
            else dp[i][j] = dp[i][j - 1];
            mx = max(mx, a[j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        int mx = -1;
        for (int j = 1; j <= n; ++j) {
            if (b[j] > mx) upd(dp[j][i], dp[j - 1][i] + 1);
            else dp[j][i] = dp[j - 1][i];
            mx = max(mx, b[j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int res = dp[i][j] + dp[n - i + 1][n - j + 1];
            upd(f[i + j - 1], res);
            upd(g[n - i + j], res);
        }
    }
    for (int i = 1; i <= n; ++i) sum[i] = (sum[i - 1] + f[i]) % mod;
    for (int i = 1; i <= n; ++i) {
        tmp[n - i + 1] = (tmp[n - i + 2] + g[n - i + 1]) % mod;
        upd(ans, 1ll * tmp[n - i + 1] * sum[i - 1] % mod);
    }
    for (int i = 1; i <= n; ++i) {
        if (f[i] + g[i + 1] == ans) ++cnt;
    }
    printf("%d %d\n", ans, cnt);
    return 0;
}