y总在直播里讲的很详细了,我就将y总的话用文字表示出来供大家参考。
状压DP
- 先预处理出来每组合法组合的兼容性,枚举每个状态
i
的所有子集j
,利用g[j]
可以转移得到f[i]
。 - 转移方程$f[i]=f[i-j]+g[j]$
class Solution {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
int n = nums.size();
vector<int> g(1 << n , -1);//g[i]表示一种合法组合的兼容性
vector<int> f(1 << n , 0x3f3f3f3f);//f[i]表示选取下标组合是i的二进制表示的最小兼容性和
f[0] = 0;
for(int i = 1 ; i < 1 << n ; i++)//预处理g
if(__builtin_popcount(i) == n / k)//如果i中1的个数等于n/k
{
vector<int> d;
for(int j = 0 ; j < n ; j++)
if(i >> j & 1)
d.push_back(nums[j]);
sort(d.begin() , d.end());
bool flag = false;
for(int i = 0 ; i < d.size() - 1 ; i++)
if(d[i] == d[i + 1])//如果存在相同的两个数说明不合法
{
flag = true;
break;
}
if(flag) continue;
g[i] = d.back() - d[0];//该组合的兼容性等于最大值-最小值(因为已经排过序,所以直接最后一个-第一个就可以)
}
for(int i = 1 ; i < 1 << n ; i++)
for(int j = i ; j ; j = (j - 1) & i)//枚举i的所有子集
if(g[j] != -1)//i的一个子集j是合法的,则转移
f[i] = min(f[i] , f[i - j] + g[j]);
int res = f[(1 << n) - 1];//答案就是选取所有下标的最小兼容性和
return res == 0x3f3f3f3f ? -1 : res;
}
};