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();
}

全部评论

相关推荐

自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务