小杨排队（dp)
鏈接：https://ac.nowcoder.com/acm/contest/3667/J
題目描述
小陽想要買個東西，然后就去了商店，發現進商店需要排隊（生意太火爆！），然后就開始漫長的等待，他覺得自己
太無聊，便開始思考一個問題，這個隊伍的人每個人可以做兩種操作，插到隊頭或者隊尾，然后問你最小的操作次數
使隊伍有序
太無聊，便開始思考一個問題，這個隊伍的人每個人可以做兩種操作，插到隊頭或者隊尾，然后問你最小的操作次數
使隊伍有序
輸入描述:
第一行 輸入一個t，代表數據組數(1<=t<=10)
第二行 輸入一個n，代表n個人在這里排隊（1<=n<=500000）
第三行 這一行n個數，是n個數的排列，代表每個人的身高
輸出描述:
有t行，每行一個數，代表最小的操作次數使它有序
示例1
輸入
復制
2
5
1 3 5 2 4
3
2 3 1
輸出
復制
3
1 AC代碼：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=,f=;char c=getchar();while(c!='-'&&(c<''||c>''))c=getchar();if(c=='-')f=-,c=getchar();while(c>=''&&c<='')x=x*+c-'',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e7+;
int a[maxn],dp[maxn];
int main()
{
int t;
t=read();
while(t--){
int n;
n=read();
for(int i=;i<=n;i++){
a[i]=read();
dp[i]=;
}
int ans=;
for(int i=;i<=n;i++){
dp[a[i]]=max(dp[a[i]-]+,dp[a[i]]);
ans=max(dp[a[i]],ans);
}
printf("%d\n",n-ans);
}
return ;
}
總結
- 上一篇： 取汉子拼音首字母的VB.Net方法
- 下一篇： ingress controller 和