题解：CF1730F Almost Sorted

zyn0309 · 2026-01-27 15:46:04 · 题解

\text{Link}

发现题目限制形如：最大的已经填入的数减小于这个数的最大的没有填的数 \le k。

考虑按照 p_i 的值从小到大填，dp_{i,s} 为最长的已经填了的前缀为 [1,i]，[i+1,i+1+k] 填入的集合为 s，转移直接枚举填哪个数即可。

逆序对的贡献 [1,i] 这部分可以对于 (i,p_i) 这样的点对做二维前缀和，[i+1,i+1+k] 的贡献 O(k) 暴力算。

时间复杂度 O(nk^22^k)。

::::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define pii  pair<int,int> 
const int N=5e3+10,inf=1e9;
int n,k,p[N],q[N],sum[N][N],dp[N][1<<9];
inline pii trans(int s,int j){
    int cnt=0;
    s|=1<<(j-1);
    while(s&1){
      s>>=1;
      ++cnt;
    }
    return pii(cnt,s);
}
inline int getval(int pos,int s,int j){
    int cnt=0;
    for(int i=1;i<=k&&pos+i<=n;++i){
      if(!((s>>(i-1))&1))continue;
      cnt+=(q[pos+i]>q[pos+j]);
    }
    return cnt;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i){
      cin>>p[i];
      q[p[i]]=i;
      ++sum[p[i]][i];
    }
    for(int i=1;i<=n;++i)
    for(int j=n;j>=1;--j)
      sum[i][j]+=sum[i-1][j]+sum[i][j+1]-sum[i-1][j+1];
    ++k;
    int limit=1<<k;
    for(int i=0;i<=n;++i)
    for(int s=0;s<limit;++s)
      dp[i][s]=inf;
    dp[0][0]=0;
    for(int i=0;i<n;++i)
    for(int s=0;s<limit;++s)
    for(int j=1;j<=k&&i+j<=n;++j){
      if((s>>(j-1))&1)continue;
      pii p=trans(s,j);
      p.first+=i;
      dp[p.first][p.second]=min(dp[p.first][p.second],dp[i][s]+sum[i][q[i+j]]+getval(i,s,j));
    }
    cout<<dp[n][0]<<"\n";
    return 0;
}

::::