题解：CF1398D Colored Rectangles

Clover_Lin · 2025-05-01 11:16:55 · 题解

前言

看串行了……看成 R,G,B\le 2000 了没往三维 DP 想……

赛后看了正解，回忆起了熟悉的棍子。

题目大意

有 R 对红色的棍子，第 i 对长度为 r_i。

有 G 对绿色的棍子，第 i 对长度为 g_i。

有 B 对蓝色的棍子，第 i 对长度为 b_i。

现在用两种不同颜色的棍子组成长方形，问面积之和的最大值是多少。

思路

实际上的数据范围：R,G,B\le200，所以时间复杂度和空间复杂度均可以为 O(RGB)，考虑三维 DP。

令 f_{i,j,k} 表示前 i 个红色棍子、前 j 个绿色棍子、前 k 个蓝色棍子的最大总面积。

我们考虑一下每一次都有哪些转移的可能性：

• 红 + 绿：此时答案为 f_{i-1,j-1,k}+r_i\cdot g_j。
• 绿 + 蓝：此时答案为 f_{i-,j-1,k1}+g_j\cdot b_k。
• 蓝 + 红：此时答案为 f_{i-1,j,k-1}+b_k\cdot r_i。

所以 f_{i,j,k} 就是上述值的最大值。

我们在具体实现的时候要对三个数组进行排序，从小到大或者从大到小都可以。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int R, r[210];
int G, g[210];
int B, b[210];
int f[210][210][210];

int main()
{
    cin >> R >> G >> B;
    for (int i = 1; i <= R; i++)
        cin >> r[i];
    sort(r + 1, r + R + 1);
    reverse(r + 1, r + R + 1);
    for (int i = 1; i <= G; i++)
        cin >> g[i];
    sort(g + 1, g + G + 1);
    reverse(g + 1, g + G + 1);
    for (int i = 1; i <= B; i++)
        cin >> b[i];
    sort(b + 1, b + B + 1);
    reverse(b + 1, b + B + 1);
    int ans = 0;
    for (int i = 0; i <= R; i++)
        for (int j = 0; j <= G; j++)
            for (int k = 0; k <= B; 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 (k && i) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + b[k] * r[i]);
                ans = max(ans, f[i][j][k]);
            }
    cout << ans << endl;
    return 0;
}