E题解
#动态规划 #dp优化
题目链接
题意
给你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(); }