简单dp，用数组存放个位数和最大位数，类似与最大上升子序列，dp[i]表示以i为结尾的最长子序列，答案即为n-最大dp[i],

解题思路:

注意事项:

#include <bits/stdc++.h> 

#define int long long

using namespace std;

const int N=100010;

int a[N],f[N],b[N],dp[11];

int n;

signed main()

{

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>a[i];

}

for(int i=1;i<=n;i++)

{

int c=a[i];

b[i]=a[i]%10;

while(c)

{

f[i]=c%10;

c=c/10;

}

}

for(int i=1;i<=n;i++)

{

for(int j=1;j<=9;j++)

{

if(dp[j]==0&&f[i]==j)

{

dp[b[i]]=max(dp[b[i]],(long long)1);

break;

}

if(f[i]==j)

{

dp[b[i]]=max(dp[f[i]]+1,dp[b[i]]);

break;

}

}

}

int ans=0;

    for(int i=1;i<=9;i++)

    {

    ans=max(ans,dp[i]);

}

cout<<n-ans;

return 0;

}

参考代码: