题目背景

众所周知，XG_Zepto 是一位来自 FZOI 的神仙。他觉得眼下的比赛太简单了，就用扫雷的时间出了一道数学题给 kal0rona。kal0rona 太菜了，看不懂题也不会写，之后求救于你了。

题目思路

很好的一道计数 DP，出自神仙组长 XG_Zepto 之手。首先，设\(f[i][j]\)为长度为\(i\)，换弹次数为\(j\)时满足条件的排列数量。之后，考虑枚举第\(i\)个数字出现的位置\(k\)，对于位置\(k\)后面的数字是不会有特殊贡献的（贡献为\((i-k)!\)），而对于前面的数，可以进行枚举前一段进行转移，一共有\({k-1}\choose{i-1}\)种选数字的方案和\(f[i-1][j-1\)种排列，乘起来即可，也就是：

\[ F[i][j] = \sum_{k = 1}^{i}f[k-1][j-1]* {{k-1} \choose {i-1}} *(i-1)! \]

可以化简，并用前缀和优化：

\[ F[i][j] = (i-1)!\sum_{k=1}^{i}\frac{f[k-1][j-1]}{(k-1)!} \]

代码

// U63113.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5050, mod = 998244353;
ll f[MAX_N], prefix[MAX_N], level[MAX_N], inv[MAX_N], n, m;
ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    level[0] = 1, inv[0] = 1;
    for (int i = 1; i <= n; i++)
        level[i] = level[i - 1] * i % mod;
    inv[n] = quick_pow(level[n], mod - 2);
    for (int i = n; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    for (int i = 0; i <= n; i++)
        prefix[i] = 1;
    for (int j = 1; j <= m; j++)
    {
        for (int i = j; i <= n; i++)
            f[i] = prefix[i - 1] * level[i - 1] % mod;
        for (int i = j; i <= n; i++)
            prefix[i] = f[i] * inv[i] % mod;
        for (int i = j + 1; i <= n; i++)
            prefix[i] = (prefix[i] + prefix[i - 1]) % mod;
    }
    printf("%lld", f[n]);
    return 0;
}

主要思路

这道题算是非常的毒瘤了。

首先我们来看第一问，根据 XG 巨佬的话，是非常明显的。我们在序列读入时减去元素自己的序号，找 LIS 长度即可。代码：

scanf("%lld", &n);
for (ll i = 1; i <= n; i++)
    scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
for (ll i = 2; i <= n; i++)
{
    ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
    len = max(len, addr);
    dp[i] = addr;
    dst[addr] = min(dst[addr], arr[i]);
}
printf("%lld\n", n - dp[n]);

第二问我们引出一个小的结论：如果要把区间\([l\dots r]\)之间变得“好看”，那么这个子区间内一定分为两段：高度为\(arr[l]\)的一段和高度\(arr[r]\)的一段。注意，此时\(arr[]\)内的元素已经剪去了元素编号。

所以这第二问就是一道区间 DP，时间复杂度为\(O(n^3)\)。不过好在序列随机，且我们可以使用邻接表预先存好那些可以处理的区间，然后进行 DP。

代码

// P2501.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll MX_N = 35020, INF = 0x3f3f3f3f;
ll head[MX_N], arr[MX_N], n, len, dst[MX_N], dp[MX_N], M_curt, f[MX_N], sum1[MX_N], sum2[MX_N];
struct edge
{
    ll to, nxt;
} edges[MX_N << 1];
void addpath(ll src, ll dst)
{
    edges[M_curt].to = dst, edges[M_curt].nxt = head[src];
    head[src] = M_curt++;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
    dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
    for (ll i = 2; i <= n; i++)
    {
        ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
        len = max(len, addr);
        dp[i] = addr;
        dst[addr] = min(dst[addr], arr[i]);
    }
    printf("%lld\n", n - dp[n]);
    for (ll i = n; i >= 0; i--)
        addpath(dp[i], i), f[i] = INF;
    f[0] = 0;
    for (ll i = 1; i <= n; i++)
        for (ll e = head[dp[i] - 1]; e != -1; e = edges[e].nxt)
        {
            ll v = edges[e].to;
            if (v > i)
                break;
            if (arr[v] > arr[i])
                continue;
            for (ll k = v; k <= i; k++)
                sum1[k] = abs(arr[k] - arr[v]), sum2[k] = abs(arr[k] - arr[i]);
            for (ll k = v + 1; k <= i; k++)
                sum1[k] += sum1[k - 1], sum2[k] += sum2[k - 1];
            for (ll k = v; k <= i - 1; k++)
                f[i] = min(f[i], f[v] + sum1[k] - sum1[v] + sum2[i] - sum2[k]);
        }
    printf("%lld", f[n]);
    return 0;
}