题目大意
一个排列\(p\)分数为\(p\)的最长上升子序列的长度，代价为满足\(\sum_{j=1}^{i-1}[p_j>p_i]<a_{i}\)的\(i\)的数量
给定\(\{a_n\}\)，对于\(\forall k\in[1,n]\)，求分数大于等于\(k\)的排列的代价的最小值
题解
玄妙优化\(dp\)题
我们可以考虑求出代价为\(k\)的排列分数的最大值，这个反过来就可以得到题目所求
考虑代价为\(0\)的排列分数的最大值，设\(f_{i,j}\)表示考虑了前\(i\)个数，从小到大排名为\(j\)的数为结尾的最长上升子序列长度
第一种转移，第\(i\)个数为第\(k\)名，原来\([1,k-1]\)名的数排名不动，\(k\)最大取\(i-a_i\)
第二种转移，第\(i\)个数为第\(k\)名，原来\([k,i-1]\)名的数排名上升一位
\[f_{i-1,j-1}\rightarrow f_{i,j} \]第三种转移，第\(i\)个数为第\(j\)名，可以从排名小于\(j\)的数转移过来
\[\max_{k=1}^{j-1}f_{i-1,k}+1\rightarrow f_{i,j}(j\leq i-a_i) \]仔细思考，发现第一种转移是不必要的，因为不如直接让第\(i\)个数为第\(j\)名，从排名小于\(j\)的数转移，这样肯定是不劣的，第三种转移也可以优化，对于一个\(k\)，转移到\(j>k+1\)是不优的
于是转移变成，\(f_{i,j}=f_{i-1,j-1}+[j\leq i-a_i]\)
\(f_{n,j}=\sum_{i=1}^j[j-i+1\geq n-i+1-a_{n-i+1}]=\sum_{i=1}^j[j\leq n-a_{n-i+1}]\)
一个\(a_i\)对\(f\)的影响是一段区间，可以用差分算出，\(\max_{j=1}^nf_{n,j}\)，即为代价为\(0\)时的分数最大值
接下来考虑代价，假设让\(i\)位产生代价\(1\)，可以理解将\(dp\)转移时的\(f_{i,j}=f_{i-1,j-1}+[j\leq i-a_i]\)变为\(f_{i,j}=f_{i-1,j-1}+1\)，对最终\(f\)的影响是使得\(j\in[n-a_i+1,n],f_{n,j}\)加\(1\)，那么可以贪心的按\(a_i\)从大到小开始产生代价，\(a_i\)的排序可以用桶排实现
时间复杂度为\(O(n)\)
\(\text{code}\)
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=3e5+1000;
int n,a[N+10],f[N+10],g[N+10],h[N+10];
int main()
{
// freopen("ARC180E.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),g[n-a[i]+1]++;
for(int i=1;i<=n;i++) f[n-i+1]++,f[n-a[i]+1]--;
for(int i=1;i<=n;i++) f[i]+=f[i-1];
for(int i=n;i>=1;i--) f[i]=max(f[i],f[i+1]);
for(int i=1;i<=n+1;i++) h[i]=n;
h[f[1]]=0;
int res=0;
for(int i=1;i<=n;i++)
{
h[f[i]+res]=min(h[f[i]+res],res);
while(g[i])
{
res++,g[i]--;
h[f[i]+res]=min(h[f[i]+res],res);
}
}
for(int i=n;i>=1;i--) h[i]=min(h[i],h[i+1]);
for(int i=1;i<=n;i++) printf("%d ",h[i]);
return 0;
}