算法1
线性DP(二维数组,行表示终点元素位置,列表示距离)
参考文献
最长上升子序列
C++ 代码
#include<iostream>
using namespace std;
const int N = 1010;
int main(){
int n;
while(cin>>n){
int f[N][N],w[N];
int res = 1;
for(int i = 1;i <= n;i++){
cin>>w[i];
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
f[i][j] = 1;
}
}
for(int i = 1;i <= n;i++){
for(int d = 1;d < i;d++){
if(w[i] >= w[i-d]) f[i][d] = max(f[i][d],f[i-d][d] + 1);
}
}
for(int i = 1;i <= n;i++){
for(int d = 1;d < i;d++){
res = max(res,f[i][d]);
}
}
cout<<n-res<<endl;
}
return 0;
}