E题解

#动态规划 #dp优化

题目链接

E-相依_牛客小白月赛95 (nowcoder.com)

题意

给你n个数，每次操作可以选择两个相同的数，将这两个数及之间的所有数消除问消除所有数的最小次数，或判断不能消除

思路

考虑考虑动态规划，用dp[i]表示1~i的最小消除次数；考虑转移：首先dp[i]一定是从和a[i]值相同的点转移过来，但是如果前一段不能消除的话那么加上这一段肯定也是不能转移的，所以转移的时候判断一下前一段能否消除。发现当同一个数出现次数非常多的时候，最坏复杂度为n^2，不太能接受，考虑优化对于多个相同数，我们肯定选择前一段消除次数少的进行转移，因此用空间换时间，记录每个数值的最少消除次数

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MAXN=5e5+10;
int a[MAXN],e[MAXN],dp[MAXN];
const int inf=31415926535897;
void sol(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=inf;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        if(i==1){
            e[a[i]]=1;
            continue;
        }
        if(e[a[i]]!=0){
            dp[i]=dp[e[a[i]]-1]+1;
        }
        if(e[a[i]]==0 && dp[i-1]!=inf)e[a[i]]=i;
        else if(dp[i-1]<dp[e[a[i]]-1])e[a[i]]=i;
    }
    if(dp[n]==inf){cout<< -1<<endl;return ;}
    else cout<<dp[n]<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    sol();
}