BallsSeparating

作者：穆皓远

关键词：枚举 贪心 动态规划 状态压缩

题目简述

有n个盒子，每个盒子里有RGB三种颜色的小球。

第i个盒子中，RGB小球数量分别为$r_i,g_i,b_i(r_i,g_i,b_i\ge1)$。

定义一次操作为从某个盒子里移动一个小球到另一个盒子。

现在要使每个盒子里至多只有一种颜色的小球。

求最小操作次数，无解输出-1。

$1\le n\le 50,1\le r_i,g_i,b_i\le 10^6$

算法一

无解当且仅当盒子数小于3，特判即可

首先显然一个小球不会被移动多次，一个小球肯定是起点直接移到终点。

存在一种最优解，使得同种颜色小球的移动终点相同。

证明：对于任意一个方案，如果一个特定颜色小球被移动到某个盒子里，这个盒子最后只会剩下该种颜色的小球，无论移入多少相同颜色小球方案仍然合法。

所以我们枚举三种颜色的移动终点

对于终点盒子，保留的颜色是确定的

对于非终点盒子，贪心的选取每个盒子保留的颜色即可（显然应该选取最多的）。

时间复杂度$O(n^4)$

空间复杂度$O(n)$

算法二

算法一中最后枚举了所有元素，事实上我们可以提前求出所有盒子最优解的和，简单的加减运算就可以省掉最后的枚举

时间复杂度$O(n^3)$

空间复杂度$O(n)$

算法三

可以发现，如果我们确定某个盒子保留哪种颜色，该方案合法当且仅当三种颜色均在保留颜色的方案中出现

考虑使用动态规划，$dp_{i,state}$表示前$i$个盒子，出现颜色集合为$state$的最小代价

时间复杂度$O(n*2^3*3)$

空间复杂度$O(n*2^3)$或$O(n)$