DP_等差數列的最長上升子序列

題意：

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;
}