[CF1398D] Colored Rectangles

[CF1398D] Colored Rectangles - dp

Description

有三个集合，大小分别为 R,G,B，里面的数分别为 ri,gi,bi，现在选出若干对数，要求两个数来自不同集合，其权值为两个数的乘积，最大化所有数对的权值和。(R,G,B le 200, ri,gi,bi le 2000)

Solution

显然大的数应该配大的数才能产生更大的贡献

设 (f[i][j][k]) 表示 R,G,B 分别用了 i,j,k 个的最大权值和

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

#define int long long
const int N = 205;

int f[N][N][N], sr, sg, sb, r[N], g[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> sr >> sg >> sb;
    for (int i = 1; i <= sr; i++)
        cin >> r[i];
    for (int i = 1; i <= sg; i++)
        cin >> g[i];
    for (int i = 1; i <= sb; i++)
        cin >> b[i];
    sort(r + 1, r + sr + 1);
    reverse(r + 1, r + sr + 1);
    sort(g + 1, g + sg + 1);
    reverse(g + 1, g + sg + 1);
    sort(b + 1, b + sb + 1);
    reverse(b + 1, b + sb + 1);
    int ans = 0;
    for (int i = 0; i <= sr; i++)
        for (int j = 0; j <= sg; j++)
            for (int k = 0; k <= sb; k++)
            {
                if (i && j)
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k] + r[i] * g[j]);
                if (j && k)
                    f[i][j][k] = max(f[i][j][k], f[i][j - 1][k - 1] + g[j] * b[k]);
                if (i && k)
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + r[i] * b[k]);
                ans = max(ans, f[i][j][k]);
            }
    cout << ans << endl;
}