很早之前看过的趣题。
先考虑 $\text{type}=1$ 的情况。考虑一个贪心策略，每次操作将该元素操作到一个比它小的元素为止。显然这样是最优的。所以一个元素是前缀最大值时是不用操作的，容易得到 $f(A)=n-\sum_{i=1}^{n} [a_i=\max_{j=1}^ia_j]$。考虑 DP，设 $f_{i,j}$ 表示选取 $i$ 个元素有 $j$ 个元素为前缀最大值，每次插入一个最小的元素进行转移。因为插在最前面才会有贡献，于是容易得到状态转移方程 $f_{i,j}\gets f_{i-1,j-1}+(i-1)\times f_{i-1,j}$。时间复杂度 $\mathcal O(n^2)$。
再考虑 $\text{type}=2$ 的情况。我们不妨直接固定元素 $n$ 为最后一个元素，直接转化为排列的情况。
因为必然会有一个点不会被移动，所以我们可以将前面连续的一段移到序列的末尾，可以视作没有花费，但是这些移到末尾的数是一定会被操作的（因为小于元素 $n$）。这样产生的 $n$ 个新的排列的 $f(A’)$ 的最小值就是原排列的 $f(A)$。
还是设计状态 $f_{i,j}$ 表示选取 $i$ 个元素有 $j$ 个元素不用操作，考虑把最大的元素插入在两段的中间。设前面一段区间有 $p$ 个不用操作，后面一段区间有 $q$ 个不用操作。
我们可以选择直接将该元素插入，那么不用操作的个数为 $p+1$；或者将前面一段区间加上该元素一起移到序列的末尾，这样不用操作的个数应该是 $q$，所以得到状态转移方程 $\displaystyle f_{i,\max {p+1,q}}\gets \binom{i-1}{j} f_{j,p}\times f_{i-j-1,q}$。通过前缀和可以做到 $\mathcal O(n^3)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=5e2+10,mod=1e9+7;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m,type;
int C[N][N],f[N][N];
inline int adj(int x){return (x>=mod)?x-mod:x;}
inline void init()
{
for(int i=0;i<=n;i++)C[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
C[i][j]=adj(C[i-1][j]+C[i-1][j-1]);
}
int main()
{
read(n,m,type);
m=n-m;
if(type==1)
{
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=adj(f[i-1][j-1]+1ll*(i-1)*f[i-1][j]%mod);
printf("%lld\n",f[n][m]);
}
if(type==2)
{
n--,m--;
init();
f[0][0]=1;
for(int i=1;i<=n;i++)f[0][i]=f[1][i]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<i;j++)
for(int k=1;k<=n;k++)
f[i][k]=adj(f[i][k]+1ll*C[i-1][j]*f[j][k-1]%mod*f[i-j-1][k]%mod);
printf("%lld\n",adj(f[n][m]-f[n][m-1]+mod));
}
return 0;
}
|