[CF1038E] Maximum Matching

[CF1038E] Maximum Matching - 区间dp

Description

给你(n)个色块，每个色块两端分别有一种颜色，并且每个色块都有一个权值，你可以将一个色块翻转，例如 ([col1mid valmid col2] o [col2mid valmid col1])，如果两个色块接触的两端颜色相同，就可以称这两个色块为一个序列，一个序列可能由多个色块构成，序列的值为构成ta的色块值的和，求所有情况下所有序列的最大值

Solution

区间 dp，(f[l][r][cl][cr]) 表示从 ([l,r]) 区间中形成一个左边是 (cl) 右边是 (cr) 的段，得分的最大值

区间 dp 怎么去处理不需要全选的情况？枚举一个分割点对两边取 max 即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

int f[105][105][5][5], a[105], b[105], val[105];
int n, m;

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> val[i] >> b[i];

    memset(f, -0x3f, sizeof f);

    for (int i = 1; i <= n; i++)
        f[i][i][a[i]][b[i]] = f[i][i][b[i]][a[i]] = val[i];

    int ans = 0;
    for (int l = n; l >= 1; l--)
    {
        for (int r = l; r <= n; r++)
        {
            for (int cl = 1; cl <= 4; cl++)
            {
                for (int cr = 1; cr <= 4; cr++)
                {
                    for (int k = l; k < r; k++)
                    {
                        f[l][r][cl][cr] = max(f[l][r][cl][cr], f[l][k][cl][cr]);
                        f[l][r][cr][cl] = max(f[l][r][cl][cr], f[l][k][cl][cr]);
                        f[l][r][cl][cr] = max(f[l][r][cl][cr], f[k + 1][r][cl][cr]);
                        f[l][r][cr][cl] = max(f[l][r][cl][cr], f[k + 1][r][cl][cr]);
                        for (int ck = 1; ck <= 4; ck++)
                        {
                            f[l][r][cl][cr] = max(f[l][r][cl][cr], f[l][k][cl][ck] + f[k + 1][r][ck][cr]);
                            f[l][r][cr][cl] = max(f[l][r][cl][cr], f[l][k][cl][ck] + f[k + 1][r][ck][cr]);
                        }
                    }
                    ans = max(ans, f[l][r][cl][cr]);
                    ans = max(ans, f[l][r][cr][cl]);
                }
            }
        }
    }

    cout << ans << endl;
}