牛客小白月赛38 -C 糟糕的打谱员

  • 参考了排名前面的大佬的代码进行了一定的优化

  • 题意描述:给定一个长度为N且有两个元素c,a的序列，其中0<=c<=1,<=a<=10，要求找出一个长度最长的子序列且使得前后两项的c,a两个元素均不相同

  • 根据题意我们很自然的能够想到使用线性dp

  • 我们开始时想到定义状态f[i] [c[i]] [a[i]] 表示在前i项的最长子序列

  • 但我们发现在推导状态转移方程时，前一个状态的i难以判断，需要进行记录

  • 但我们想要记录前面的i无疑需要条件作为数组的下标

  • 联想到了用c和a用来记录

  • 而我们因此可以采用一个pre[c] [a]来记录我们想要的c，a两元素对应最近的位置

  • 上一次c[i]=c,a[i]=a的i序号

  • 而因为pre数组中已经有了关于c，a的信息，我们自然想到在f中可以略去

  • 得到优化后的状态转移方程：

  • ac代码：

    #include<bits/stdc++.h>
using namespace std;
#define maxn 300005
int T,n;
int c[maxn],a[maxn];
int f[maxn],pre[maxn][15];
// 找到一个最长序列，满足前后落子人和落子点不同
// 状态转移方程
int main(){
  cin>>T;
  while(T--){
      memset(f,0,sizeof f);
      memset(pre,0,sizeof pre);
      int ans=0;
      cin>>n;
      for(int i=1;i<=n;i++){
          cin>>c[i]>>a[i];
      }
      for(int i=1;i<=n;i++){
          for(int j=1;j<=10;j++){
              if(a[i]==j)continue;
              f[i]=max(f[i],f[pre[c[i]^1][j]]+1);
              pre[c[i]][a[i]]=i;
              ans=max(ans,f[i]);
          }

      }
      cout<<ans<<endl;
  }

  return 0;
}