题解

思路推导

同一种颜色内部，较长的木棍应该优先参与配对。把三组长度分别从大到小排序后，若某种颜色已经使用了前若干对木棍，那么下一次使用这种颜色时只需考虑当前尚未使用的第一对。交换论证可知，跳过更长木棍而使用更短木棍不会使答案更优。

因此，状态只需记录三种颜色分别使用了多少对木棍。一次新建矩形会同时推进其中两种颜色的下标，共有红绿、红蓝、绿蓝三种选择。

做法

设 $dp_{i,j,k}$ 表示红、绿、蓝三组分别使用了前 $i,j,k$ 对木棍时能够得到的最大总面积。

从每个状态尝试三种转移：若红色和绿色都还有木棍，则把 $r_i$ 与 $g_j$ 配成矩形；另外两种颜色组合完全类似。每次转移把相应两个下标加一，并把两根边长之积加入答案。

所有状态初值为零。遍历全部状态并更新后，所有状态中的最大值就是答案，因为允许留下任意木棍不用。

正确性证明

对于任意固定的两种颜色配对关系，若某种颜色中一根较短木棍被使用而一根较长木棍未使用，把二者交换不会改变颜色合法性，并且不会减小对应矩形面积。因此一定存在一个最优方案，使每种颜色被使用的木棍都是排序后的一个前缀。

动态规划状态准确描述了三个已用前缀。任意转移选择两种仍有剩余木棍的颜色，恰好对应新建一个合法矩形，并且每对木棍只会因下标推进而使用一次。反过来，根据前缀性质，任意最优方案的矩形可以按使用顺序还原成这些转移的某条路径。动态规划对每个状态取最大值，所以不会遗漏更优方案。遍历所有可能的终止状态后取得的最大值即为全局最优总面积。

复杂度分析

状态数为 $O(RGB)$，每个状态只有常数次转移。时间复杂度为 $O(RGB)$，空间复杂度为 $O(RGB)$。