[nk] 糟糕的打谱员 线性DP

前言

线性DP是世界上最难的算法！！(我在口胡) 前言 : https://ac.nowcoder.com/acm/contest/11215/C

思路

看完该题之后 (问的什么鬼 贪心？排序之后交替拿？ 样例都没过笑死 QAQ)

认真分析一波,转换模型

这题其实再问 满足条件的最长序列长度

条件就是 当前的 c和a 与上一个 不同 :(DP的样子出来了是不是)

因此需要求的状态就是 f[i]即当前最长的序列长度

状态转移 :

因为这个可以乱序拿 我们不能从 i-1或者 i 之前的直接枚举出来

我们可以通过 a 来枚举 (因为他才10)

所以我们可以通过 ^(异或) 以及一个 pre 数组 枚举a 然后来进行状态转移

即 f [ i ] = max ⁡ ( f [ i ] , f [ pre ⁡ [ c [ i ] ∧ 1 ] [ j ] ] + 1 ) f[i]=\max \left(f[i], f\left[\operatorname{pre}\left[c[i]^{\wedge} 1\right][j]\right]+1\right) f[i]=max(f[i],f[pre[c[i]∧1][j]]+1)

因此这样子就简单的推下来了

(可真 简单 是吧？)

CODE

/**
f[i]表示当前合法的长度

可以由 前面不一样的推导过来
f[i]  = f[c[i][j]]
**/
#include 
using namespace std;
const int N = 3e5+10;
int t,n;
int c[N],a[N],f[N],pre[N][15];
void solve()
{
    memset(f,0,sizeof f);
    memset(pre,0,sizeof pre);

    int ans = 0 ;
    cin>>n;
    for(int i=1;i>c[i]>>a[i];

    for(int i=1;i