Problem: 1681. 最小不兼容性挺难的动态规划的题目不会做看了题解的还看了豆包给的答案下面是参考豆包给的答案写的做了一点优化的先拿到所有小组每个小组都是group_sz个数字然后动态规划求解最终的答案需要满足当前和之前的没有交集才行Code#include vector #include algorithm #include unordered_map #include climits using namespace std; class Solution { public: int minimumIncompatibility(vectorint nums, int k) { int n nums.size(); int group_sz n / k; if(n % k ! 0) return -1; unordered_mapint, int ump; for(int i : nums) ump[i]; for(auto [key, value]: ump) { if(value k) return -1; } int right (1n) ; vectorpairint, int umnap; for(int i 1; i right; i) { if(__builtin_popcount(i) group_sz) { int vis 0, good 1, mx 0, mi 20; for(int j 0; j n; j) { if( ((1j) i) 0 ) { if((vis (1nums[j])) 0) { good -1; break; } vis | (1nums[j]); mi min(mi, nums[j]); mx max(mx, nums[j]); } } if( good 0 ) umnap.push_back( { i, mx - mi } ); } } vectorint dp(right, 999999); dp[0] 0; for(int mask 0; mask right; mask) { if(dp[mask] 999999) continue; if(__builtin_popcount(mask) % group_sz 0) { for(auto [key, value]: umnap) { if((mask key) 0) { int newmask (mask | key); dp[newmask] min(dp[newmask], dp[mask] value); } } } } return dp[right-1] 999999? -1 : dp[right - 1]; } };