题解 CF1398D 【Colored Rectangles】

发表于

题意

给定三种颜色的棍子若干对，每次可以选取不同颜色的两对棍子组成一个矩形，最大化矩形的总面积。

$\operatorname{Sol}$

首先我们发现这么一个结论：对于长的棍子，应当尽量与长的棍子配对组成矩形，可用排序不等式证明（$\text{同序和}\ge \text{乱序和}\ge \text{逆序和}$）。

所以我们先把三种棍子分别按长度从大到小排序，再考虑 dp。

设 $f(i,j,k)$ 表示选取 $i$ 对红棍子， $j$ 对绿棍子， $k$ 对蓝棍子的矩形总面积最大值，显然有转移方程：

最后答案为 $\max f(i,j,k)$。

$\operatorname{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int R[201], G[201], B[201];
long long f[201][201][201];
bool cmp(int x, int y){return x > y;}
int main (){
    int r, g, b;
    cin >> r >> g >> b;
    for (int i = 1; i <= r; i++)cin >> R[i];
    for (int i = 1; i <= g; i++)cin >> G[i];
    for (int i = 1; i <= b; i++)cin >> B[i];
    sort(R + 1, R + 1 + r, cmp); sort(G + 1, G + 1 + g, cmp);
    sort(B + 1, B + 1 + b, cmp);
    f[1][1][0] = R[1] * G[1];
    f[1][0][1] = R[1] * B[1];
    f[0][1][1] = G[1] * B[1];
    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 (i && k)f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + R[i] * B[k]);
                if (j && k)f[i][j][k] = max(f[i][j][k], f[i][j - 1][k - 1] + G[j] * B[k]);
            }
    long long Max = 0;
    for (int i = 0; i <= r; i++)
        for (int j = 0; j <= g; j++)
            for (int k = 0; k <= b; k++)
                Max = max(Max, f[i][j][k]);
    cout << Max << endl;
    return 0;
}
+ +