这道题 O ( n 2 ) O(n^2) O(n2)的dp是很好想的。 设 f i f_i fi表示到 i i i时的队伍小于等于 r a n k i rank_i ranki最大的不用移动的个数，那么显然状态转移方程是 f i = max j = 1 j ≤ i & r a n k j ≤ r a n k i f j + 1 f_i=\max\limits_{j=1}^{j\leq i\&rank_j\leq rank_i}f_j+1 fi=j=1maxj≤i&rankj≤rankifj+1 就是从小于等于一定不用乱序的转移。 然后发现这个东西是个二维偏序，第一维本来有序，那么第二维用树状数组维护一下就好了。 代码实现:
#include<cstdio> #include<algorithm> #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; int n,m,k,ks,a[500039],s[500039],f[500039],ans,g[500039]; inline bool cmp(int x,int y){return a[x]<a[y];} inline void get(int x,int y){while(x<=n) f[x]=max(y,f[x]),x+=x&-x;} inline int find(int x){int ans=0;while(x) ans=max(f[x],ans),x-=x&-x;return ans;} int main(){ register int i,j; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) s[i]=i; sort(s+1,s+n+1,cmp); for(i=1;i<=n;i++) a[s[i]]=(i-1)/k+1; for(i=1;i<=n;i++){ g[i]=find(a[i])+1; get(a[i],g[i]); ans=max(ans,g[i]); } printf("%d\n",n-ans); }