P11187 配对序列

P11187 配对序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

考虑DP，看注释，时间复杂度 \(O(n)\)。非最优思路。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 500010;

int f[N][2]; // f[i][0/1] 前i个里面的最大子序列长度，0/1 表示两个不同末尾且0大于1 
int g[N][2]; // 表示对应f的末尾，0/1不同
int n, m;
int a[N], b[N]; // b[i]表示当前数值为i的数的下标，用于求出last数组
int last[N]; // last[i]表示与a[i]相同的上一个数的下标，用于加快DP

/* 对于 f[i] 来说要么使用当前a[i]作为序列，要么不用。
如果使用a[i],那么它一定先配对last[i],那么就用f[v = last[i] - 1]递推过来,前提f[v]所选的末尾和a[i]不同.如果不用就继承f[i-1].转移方程为 f[i] = max(f[i - 1], f[last[i] - 1] + 2);
因为非f[v]的选法可能可以和a[i]拼接,而f[v]选法不可,导致答案有漏,为了转移全面,于是记录f[i][0/1]两个末尾不同,且f[i][0]>=f[i][1],把漏掉的补上 就出现以下代码

*/
int main()
{
    cin >> n;
    
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        if (b[a[i]]) last[i] = b[a[i]];
        b[a[i]] = i;
    }
    
    for (int i = 1; i <= n; i ++ )
    {
        f[i][0] = f[i - 1][0];
        g[i][0] = g[i - 1][0];
        
        f[i][1] = f[i - 1][1];
        g[i][1] = g[i - 1][1];
        
        int v = last[i] - 1;
        if (last[i] > 0) 
        {
            if (g[v][0] != a[i]) // 第一个可以
            {
                if (f[i][0] < f[v][0] + 2) 
                {
                    f[i][1] = f[i][0];
                    g[i][1] = g[i][0];
                    f[i][0] = f[v][0] + 2;
                    g[i][0] = a[i];
                }
                else if (f[i][1] < f[v][0] + 2) 
                {
                    f[i][1] = f[v][0] + 2;
                    g[i][1] = a[i];
                }
                else if (f[i][1] == f[v][0] + 2 && g[i][1] == g[i][0])
                {
                    g[i][1] = a[i];
                }
            }
            
            if (g[v][1] != a[i])
            {
                if (f[i][0] < f[v][1] + 2) 
                {
                    f[i][1] = f[i][0];
                    g[i][1] = g[i][0];
                    f[i][0] = f[v][1] + 2;
                    g[i][0] = a[i];
                }
                else if (f[i][1] < f[v][1] + 2)
                {
                    f[i][1] = f[v][1] + 2;
                    g[i][1] = a[i];
                }
                else if (f[i][1] == f[v][1] + 2 && g[i][1] == g[i][0])
                {
                    g[i][1] = a[i];
                }
            }
        }
        if (f[i][1] > f[i][0]) 
        {
            swap(f[i][1], f[i][0]);
            swap(g[i][1], g[i][0]);
        }
        
    }
    cout << f[n][0] << endl;
    
    return 0;
}