51nod 1241 特殊的排序(动态规划)
分析:记数组中最长的连续子串长度为maxlen(数值上连续,位置不一定连续,如2134,最长为3).首先可以证明,n-maxlen次操作可以满足条件,如最长子串最后一个为x<n,则把x+1移到最后,如果是x=n,记子串的第一个为y,把y-1移到最前,每次操作后最长连续子串长度+1,故可以满足条件.接下来证明,这是最少的移动次数.假设还有更少的,说明存在一步移动,最长连续子串长度至少+2,但移走一个元素不增加长度,把这个元素放在最前或最后最多只能增加1,矛盾.
求maxlen动态规划一下,记dp[x]为数字x开头的最长连续子串长度,则if(x+1在x后面)dp[x]=dp[x+1]+1,else dp[x]=1.复杂度为O(n).
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int maxn=50005; 5 int n,dp[maxn],loca[maxn]; 6 int main(){ 7 memset(dp,0,sizeof(dp)); 8 cin>>n; 9 int a; 10 for(int i=0;i<n;i++){ 11 cin>>a; 12 loca[a-1]=i; 13 } 14 dp[n-1]=1; 15 for(int i=n-2;i>=0;i--){ 16 if(loca[i+1]>loca[i]) 17 dp[i]=dp[i+1]+1; 18 else 19 dp[i]=1; 20 } 21 int maxlen=0; 22 for(int i=0;i<n;i++){ 23 if(dp[i]>maxlen)maxlen=dp[i]; 24 } 25 cout<<n-maxlen<<endl; 26 return 0; 27 }