题意:
1241 特殊的排序
一个数组的元素为1至N的整数,现在要对这个数组进行排序,在排序时只能将元素放在数组的头部或尾部,问至少需要移动多少个数字,才能完成整个排序过程?
例如:
2 5 3 4 1 将1移到头部 =>
1 2 5 3 4 将5移到尾部 =>
1 2 3 4 5 这样就排好了,移动了2个元素。
给出一个1-N的排列,输出完成排序所需的最少移动次数。
输入
第1行:1个数N(2 <= N <= 50000)。
第2 - N + 1行:每行1个数,对应排列中的元素。
输出
输出1个数,对应所需的最少移动次数。
输入样例
5
2
5
3
4
1
输出样例
2
思路:
其实就是找一个序列中最长的,差为1的等差数列的长度。。。用n减掉就是答案了。。。
但是最长上升子序列会T掉的,wuwuwu,我这种菜鸡就只能想到最长上升子序列。。。好菜啊!!!!
代码实现:
先看正确的吧:(等差数列的优化真的优化挺多的,学到了!!!)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int dp[maxn];
int main(){
int n;
int a[maxn];
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
}
int ans = 1;
for(int i = 1;i <= n;i++){
dp[a[i]] = dp[a[i] - 1] + 1;//----------重点在这里
ans = max(ans,dp[a[i]]);
}
printf("%d\n",n - ans);
return 0;
}
T掉的最长上升子序列。。。嘤嘤嘤!!
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int dp[maxn];
int main(){
int n;
int a[maxn];
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
}
dp[0] = 1;
int ans = 1;
for(int i = 1;i <= n;i++){
dp[i] = 1;
for(int j = 1;j < i;j++){
if(a[i] > a[j]&&a[i] - a[j] == 1){
dp[i] = max(dp[i],dp[j] + 1);
ans = max(ans,dp[i]);
}
}
}
printf("%d\n",n - ans);
return 0;
}