【20 分】位运算枚举染色

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
int T;
int n;
int a[MAXN + 5];
int c[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        int ans = 0;
        for (int sta = 0; sta < (1LL << n); sta++)
        {
            // 当前染色状态是 sta
            for (int i = 0; i < n; i++)
            {
                // 找最近的同色
                int pos = -1;
                for (int j = i - 1; j >= 0; j--)
                    if (((sta >> j) & 1) == ((sta >> i) & 1))
                    {
                        pos = j;
                        break;
                    }
                if (pos == -1 || a[pos] != a[i])
                    c[i] = 0;
                else
                    c[i] = a[i];
            }
            int now = 0;
            for (int i = 0; i < n; i++)
                now += c[i];
            ans = max(ans, now);
        }
        cout << ans << "\n";
    }
    return 0;
}

【20 分】dfs 枚举染色

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
int T;
int n;
int a[MAXN + 5];
int c[MAXN + 5];
int color[MAXN + 5];
int ans;
void dfs(int now)
{
    if (now > n)
    {
        // 当前染色状态是 color[1~n]
        int now = 0;
        for (int i = 1; i <= n; i++)
        {
            // 找最近的同色
            int pos = 0;
            for (int j = i - 1; j >= 1; j--)
                if (color[j] == color[i])
                {
                    pos = j;
                    break;
                }
            if (pos != 0 && a[pos] == a[i])
                now += a[i];
        }
        ans = max(ans, now);
        return;
    }
    color[now] = 1;
    dfs(now + 1);
    color[now] = 0;
    dfs(now + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        ans = 0;
        dfs(1);
        cout << ans << "\n";
    }
    return 0;
}

【50 分】基础 $O(n^2)$ 的 dp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
int T;
int n;
int a[MAXN + 5];
// 前 i 项、第 i 项为 j 颜色、上一个异色为 k 位置的最大得分
int f[MAXN + 5][2][MAXN + 5];
int now(int i, int j)
{
    if (a[i] == a[j])
        return a[i];
    else
        return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                f[i][0][j] = f[i][1][j] = 0;
            // 上一个异色的位置是 j（j==0 表示没有异色），不是左边的时候
            // 上一个同色的位置就是 i-1
            for (int j = 0; j <= i - 2; j++)
            {
                f[i][0][j] = f[i - 1][0][j] + now(i, i - 1);
                f[i][1][j] = f[i - 1][1][j] + now(i, i - 1);
                ans = max(ans, f[i][0][j]);
                ans = max(ans, f[i][1][j]);
            }
            // 上一个异色的位置是 i-1，找上一个同色的位置
            for (int j = 0; j <= i - 2; j++)
            {
                f[i][0][i - 1] = max(f[i][0][i - 1],
                                     f[i - 1][1][j] + now(i, j));
                f[i][1][i - 1] = max(f[i][1][i - 1],
                                     f[i - 1][0][j] + now(i, j));
            }
            ans = max(ans, f[i][0][i - 1]);
            ans = max(ans, f[i][1][i - 1]);
        }
        cout << ans << "\n";
    }
    return 0;
}

【50 分】显然中间那个维度没必要

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
int T;
int n;
int a[MAXN + 5];
// 前 i 项、上一个异色为 j 位置的最大得分
int f[MAXN + 5][MAXN + 5];
int now(int i, int j)
{
    if (a[i] == a[j])
        return a[i];
    else
        return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                f[i][j] = 0;
            // 上一个异色的位置是 j（j==0 表示没有异色），不是左边的时候
            // 上一个同色的位置就是 i-1
            for (int j = 0; j <= i - 2; j++)
            {
                f[i][j] = f[i - 1][j] + now(i, i - 1);
                ans = max(ans, f[i][j]);
            }
            // 上一个异色的位置是 i-1，找上一个同色的位置
            for (int j = 0; j <= i - 2; j++)
                f[i][i - 1] = max(f[i][i - 1],
                                  f[i - 1][j] + now(i, j));
            ans = max(ans, f[i][i - 1]);
        }
        cout << ans << "\n";
    }
    return 0;
}