出题人怎么这么牛 - 洛谷保存站

优美，太优美。

注意到逆序对和 $\text{LIS}$ 都是只用关注相对大小的，所以设计状态的时候大抵是要跟相对大小的排名有关的。

$\text{LIS}$ 并不好放入状态，考虑将其设为 $\text{dp}$ 数组的答案。

那么考虑将成本为 $0$ 的时候最大得分是多少（转换一下把个数大于等于 $a_i$ 看成有贡献的）。

设 $f_{i,j}$ 表示考虑了前 $i$ 个位置，$\text{LIS}$ 以**第 $j$ 大** 数为结尾的最长长度是多少。
$$
f_{i,j}=\max\begin{cases}
f_{i-1,j}   \\
f_{i-1,j-1} & j> a_i+1 \\
f_{i-1,k}+1  & k\ge j> a_i
\end{cases}
$$
$\max f_{n,i}$  即为最长 $\text{LIS}$。

根据定义我们可以推出 $f_{i,j}\le f_{i,j+1}+1$，因为交换第 $j$ 大和第 $j+1$ 大答案之多变化 $1$。

再仔细一看，发现第二种转移是无用的。

然后你注意到 $k>j$ 的转移也是无用的，因为你每次更新都是 $j$ 较大的答案才有可能变大，那对于 $k$，转移到 $k>j$ 肯定是不优没有转移到 $k=j$ 优的。

那么现在的转移变为：
$$
f_{i,j}=f_{i-1,j}+[j>a_i]
$$
那么对于每一列分别考虑，最终答案即为：
$$
g_i=\sum_{j\ge i}a_j< i\\
ans=\max_{i=1}^{n} g_i
$$
现在再考虑成本不为 $0$，成本加 $1$ 等价于将一个 $a_j$ 变成 $0$，设成本为 $x$，那么答案即为：
$$
ans=\max(x-\max_{i=1}^{n-x+1}g_i,0)
$$
$g_i$ 差分即可求得，然后求个前缀最大值就好了。

优美，太优美。

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int n,f[N];
int main()
{
    cin>>n;
    for(int i=1,x;i<=n;i++)cin>>x,f[x+1]++,f[i+1]--;
    for(int i=1;i<=n;i++)f[i]+=f[i-1];
    for(int i=1;i<=n;i++)f[i]=max(f[i],f[i-1]);
    for(int i=1;i<=n;i++)cout<<max(i-f[n-i+1],0)<<" ";
}
```

正在渲染内容...