代码

作者： 作者的头像   代码人生 ,  2024-08-27 16:14:01 ,  所有人可见 ,  阅读 6

4 


#include <iostream>
using namespace std;
const int N = 1005;
int n;
int a[N];
int f[N][N];
int ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int d=1;d<=i;d++){
            f[i][d] = 1;
            if(a[i] >= a[i - d]){
                f[i][d] = f[i - d][d] + 1;
            }
            ans = max(ans,f[i][d]);
        }
    }
    printf("%d",n - ans);
    return 0;
}

1 评论

用户头像
Eroson   2个月前      2    踩      回复 
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int n,maxn,a[N],dp[10005];
void solve(int k){
    for (int i=1;i<=max(1,k-2);i++){
        int x=a[k],cnt=1,p=k;
        while(p-i>0){
            p-=i;
            if (a[p]<=x) cnt++,x=a[p];  
            else break;
        }
        if(cnt>dp[k]) dp[k]=cnt;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--) solve(i);
    for(int i=1;i<=n;i++) maxn=max(maxn,dp[i]);
    cout<<n-maxn;
    return 0;
}