[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], fleft[operatorname{pre}left[c[i]^{wedge} 1right][j]right]+1right) f[i]=max(f[i],f[pre[c[i]∧1][j]]+1)

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

(可真 简单 是吧？)

#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<=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<>t;
    while(t -- )
    solve();
    return 0;
}