526互联

CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)C

发布时间 2023-06-30 18:50:22作者: righting

CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)C

C(dp)

C

题目给出一个数组，我们可以在这一个数组里面找出\(a_i\)和\(a_j\)其中\(i\)和\(j\)不相等，并保证\(a_i=a_j\),这样我们就可以把\(i-j\)这一段区间的所有数字都删除，问我们怎样删除才可以使删除的数字数量最多

很明显，这是一个\(dp\)，但是如果对于每一对相同数字，根据这个得到不同的线段，然后一个一个的求，会\(TLE\)，所以我们需要一个特殊的操作让我们只需要那个最优的情况（求\(i\)之前的所有的\(max(dp_j)\)会超时，但是如果预处理出\(mx_i=max(dp_i)\),但是我们不知道这个\(mx_{i-1}\)的开始在哪一个位置，无法求出这一段的贡献

我们可以设置\(dp_i\)前\(i\)个位置的最大删除数量为多少

然后我们这里我预处理的\(mx_i=max(dp_i-i)\),这样就相当于把\(dp_i\)在\(i\)的位置看成往左挪动到位置\(0\)，这样，后面如果我们用到它，我们只要知道右端点即可，即\(dp_{i+1}=mx_{a[i]}+i+1\),代表着\(0\)到当前位置\(i\)的距离，也可以理解为\(dp_{i+1}=dp_{i-1}+i-(i-1)+1\)(如果这一个mx_a_i是从\(dp_{i-1}\)那里得来的)

这样就很好写了

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
#include <bitset>
#include <numeric>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define eps 1e-6
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int t;
int n,a[maxn];
void solve()
{
  cin>>n;
  for (int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  vector<int>dp(n+2,0),mx(n+2,-inf);
  for(int i=1;i<=n;i++)
  {
    dp[i+1]=max(dp[i],mx[a[i]]+i+1);
    mx[a[i]]=max(mx[a[i]],dp[i]-i);//mx记录的是在某一个数，并以其中一个位置作为起点的最大值，这样，后面如果要用到这一个数，我们可以直接把mx+pos+1,因为我们之前已经减去了本身的距离
  }
  int ans=dp[n+1];
  cout<<ans<<"\n";
  return ;
}
signed main ()
{
  //ios;
  cin>>t;
  while (t--)
  {
    solve();
  }
  system ("pause");
  return 0;
}