[ABC176F] Brave CHAIN 题解

· · 题解

校内测试搬了这题，想出了一个和题解区做法都不一样的做法。

首先对序列 a 分组，a_1 和 a_2 为一组，后面每三个一组，最后 a_{3n} 自己为一组，总共 n+1 组。考虑倒着 DP，h_{i,j,k} 代表完成了前 i 组剩下的两个数为 j 和 k，继续完成剩下的组的最大分数（不包括前 i 组产生的分数），这样就可以 O(n^3) 完成。

考虑另外一个切入点，如果 j 和 k 其中一个不产生贡献，那么就可以只考虑一个，那么设 g_{i,j} 代表完成了前 i 组，剩下的一个数为 j，另一个数没用，完成剩下的组的最大分数。

继续考虑 j 和 k 都会产生贡献，所以在 j 和 k 贡献之前，它们不能被删掉，那么这个过程中删除的数确定了，预处理即可。

假设 j 比 k 先产生贡献，那么一定是后面两个和 j 相同的数在同一个组别，不然 k 无法产生贡献。如果后面和 j 相同的两个数的组别不同，中间肯定要保留第一个和 j 相同的数，那么就要删除 k，所以要在同一个组别。

考虑从一开始得到 j 和 k 时就设状态，然后就可以直接跳跃到 j 被贡献的位置。由于是刚得到，那么其中一个数一定是第 i 个组的（只有三个数），那么就可以 DP 了，当然还要特判 j=k 的情况。设 f_{i,j,k} 代表完成了前 i 个组，剩下的两个数为 j 和 a_{3i-k}(1\le j\le3)，完成剩下的组的最大分数。

把 g_{i,j} 和 f_{i,j,k} 结合起来，时间复杂度 O(n^2)。

#include<cstdio>
#define N 6010
#define M 2010
using namespace std;
int n, a[N];
int f[M][M][4], g[M][M];
int fir[N][M], p[N];
void m(int &x, int y) { if(y > x)x = y; }
int noget(int s, int x)
{
    if(a[3 * s] != x)return 3;
    if(a[3 * s + 1] != x)return 2;
    return 1;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= 3 * n; i++)scanf("%d", a + i);
    for(int i = 3 * n; i; i--)
    {
        for(int j = 1; j <= n; j++)
            fir[i][j] = fir[i + 1][j];
        fir[i][a[i]] = i;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= 3; j++)
            if(a[3 * n - j] == a[3 * n] && i == a[3 * n])
                f[n][i][j] = 1;
    for(int i = 1; i <= n; i++)
        if(a[3 * i] == a[3 * i + 1] && a[3 * i] == a[3 * i + 2])
            p[i] = 1;
    for(int i = 1; i <= n; i++)
        p[i] += p[i - 1];
    for(int s = n - 1; s; s--)
    {
        for(int i = 1; i <= n; i++)
        {
            if(fir[3 * s][i] / 3 == fir[fir[3 * s][i] + 1][i] / 3 && fir[3 * s][i] / 3 == s)
            {
                int k = noget(s, i);
                m(g[s][i], g[s + 1][a[3 * s + 3 - k]] + 1);
            }
            if(a[3 * s] == a[3 * s + 1] && a[3 * s] == a[3 * s + 2])m(g[s][i], g[s + 1][i] + 1);
            m(g[s][i], f[s + 1][a[3 * s]][1]);
            m(g[s][i], f[s + 1][a[3 * s + 1]][1]);
            m(g[s][i], f[s + 1][a[3 * s]][2]);
            for(int k = 1; k <= 3; k++) m(g[s][i], f[s + 1][i][k]);
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= 3; j++)
            {
                int num = a[3 * s - j], x, y;
                m(f[s][i][j], g[s][i]);
                m(f[s][i][j], g[s][num]);
                if(num == i)
                {
                    int x = fir[3 * s][i] / 3;
                    if(x)
                    {
                        if(a[3 * x] == num) m(f[s][i][j], f[x + 1][a[3 * x + 1]][1] + 1 + p[x - 1] - p[s - 1]);
                        else if(a[3 * x + 1] == num) m(f[s][i][j], f[x + 1][a[3 * x]][1] + 1 + p[x - 1] - p[s - 1]);
                        else m(f[s][i][j], f[x + 1][a[3 * x]][2] + 1 + p[x - 1] - p[s - 1]);
                    }
                }
                if(fir[3 * s][i] / 3 == fir[fir[3 * s][i] + 1][i] / 3)x = fir[3 * s][i] / 3;
                else x = 1e9;
                if(fir[3 * s][num] / 3 == fir[fir[3 * s][num] + 1][num] / 3)y = fir[3 * s][num] / 3;
                else y = 1e9;
                if(!x)x = 1e9;
                if(!y)y = 1e9;
                if(x < y)
                {
                    int k = noget(x, i);
                    m(f[s][i][j], f[x + 1][a[3 * s - j]][k] + 1 + p[x - 1] - p[s - 1]);
                }
                else if(x > y)
                {
                    int k = noget(y, num);
                    m(f[s][i][j], f[y + 1][i][k] + 1 + p[y - 1] - p[s - 1]);
                }
            }
    }
    printf("%d", f[1][a[1]][1]);
    return 0;
}