巧克力分割问题变体 题目描述完整版你有n段连续的巧克力每一段都有一个口味值整数。现在需要将这些巧克力切成连续的k段即切k-1刀每刀切在两个相邻块之间。切完后每一段的得分定义为该段中不同口味值的种类数即该子数组中不同整数的个数。你的目标是最大化这k段得分之和并返回这个最大值。注意必须恰好切成k段不能多也不能少。 输入格式第一行两个整数n和k分别表示巧克力总段数和要切成的段数。第二行n个整数表示每段巧克力的口味值用空格分隔。 输出格式一个整数表示最大可能的总得分。⚠️ 约束条件合理假设方便你设计算法1 k n 200n 较小O(n^3) 可接受但你能做得更好口味值范围1 flavor[i] 1000或更大的整数但无关紧要 测试用例含预期输出示例 1输入 4 2 1 2 1 2 输出 4解释切成[1,2]和[1,2]两段得分各为 2总和 4。示例 2输入 5 1 1 2 3 1 4 输出 4解释不切整段不同口味为{1,2,3,4}得分 4。示例 3输入 4 2 1 1 1 1 输出 2解释无论怎么切每段得分都是 1两段总和 2。示例 4输入 5 3 1 2 3 4 5 输出 5解释切成[1,2]、[3,4]、[5]得分 2215或[1]、[2,3]、[4,5]得 1225最大为 5。示例 5复杂重叠输入 6 3 1 2 1 3 2 3 输出 6解释切成[1,2]得分2、[1,3,2]得分3、[3]得分1实际切法很多最大可为 6例如[1,2,1]得2[3,2,3]得2再加一段其实最优可达到6可尝试[1,2](2)、[1,3,2](3)、[3](1) 总6或[1](1)、[2,1,3](3)、[2,3](2) 总6正确输出6。示例 6边界k n输入 3 3 1 2 1 输出 3解释每段一个元素每段得分均为1总和3。示例 7边界k 1全相同输入 4 1 5 5 5 5 输出 1解法好这次我把重点放在**“DP 矩阵长什么样、每个格子代表什么、为什么边界这样设”**上代码写得更直白每一步都有注释。一、先建立直观DP 矩阵是一张“表”列 j 段数 0 1 2 3 ... K ┌─────┬─────┬─────┬─────┬─────┐ 行 i 0│ dp00│ dp01│ dp02│ dp03│ ... │ 前 0 个元素 ├─────┼─────┼─────┼─────┼─────┤ 1│ dp10│ dp11│ dp12│ dp13│ ... │ 前 1 个元素 ├─────┼─────┼─────┼─────┼─────┤ 2│ dp20│ dp21│ dp22│ dp23│ ... │ 前 2 个元素 ├─────┼─────┼─────┼─────┼─────┤ 3│ dp30│ dp31│ dp32│ dp33│ ... │ 前 3 个元素 ├─────┼─────┼─────┼─────┼─────┤ ... ├─────┼─────┼─────┼─────┼─────┤ n│ dpn0│ dpn1│ dpn2│ dpn3│ ... │ 前 n 个元素 └─────┴─────┴─────┴─────┴─────┘每个格子dp[i][j]回答一个问题“把数组的前i个元素flavor[0] ~ flavor[i-1]恰好切成j段最多能拿多少分”我们要的答案是右下角dp[n][K]。二、矩阵里哪些格子是“合法”的关键约束前i个元素切成j段每段至少 1 个元素所以必须i j。列 j 段数 0 1 2 3 4 ┌─────┬─────┬─────┬─────┬─────┐ 行 i 0│ 0 │ × │ × │ × │ × │ ├─────┼─────┼─────┼─────┼─────┤ 1│ × │ ✓ │ × │ × │ × │ ├─────┼─────┼─────┼─────┼─────┤ 2│ × │ ✓ │ ✓ │ × │ × │ ├─────┼─────┼─────┼─────┼─────┤ 3│ × │ ✓ │ ✓ │ ✓ │ × │ ├─────┼─────┼─────┼─────┼─────┤ 4│ × │ ✓ │ ✓ │ ✓ │ ✓ │ └─────┴─────┴─────┴─────┴─────┘dp[0][0] 0前 0 个元素切 0 段合法得分 0。dp[i][0]i 0前i个元素切 0 段不可能非法。dp[0][j]j 0前 0 个元素切j段不可能非法。对角线及右下区域i j才是合法状态。非法格子用-1或负无穷表示避免它们被错误地拿去做max。三、转移的直观含义枚举“最后一刀的左边”假设要算dp[i][j]前i个元素切j段。想象最后一刀切在t-1和t之间t是最后一段的起点下标: 0 1 2 ... t-1 | t t1 ... i-1 └──── 前 t 个 ──┘ └── 最后一段 ──┘ 切 j-1 段 得分 distinct(t, i-1)所以dp[i][j] max over t: dp[t][j-1] ← 前面 t 个元素切 j-1 段的最优解 distinct(t, i-1) ← 最后一段自己的得分t的取值范围t j-1前面t个元素要切j-1段至少需要j-1个元素。t i-1最后一段flavor[t ... i-1]必须非空。一句话dp[i][j]就是在所有可能的“最后一刀位置”里挑一个让“前面最优 最后一段得分”最大的。四、完整代码带详细注释#includebits/stdc.husingnamespacestd;classSolution{public:intmaxTotalDistinct(vectorintflavor,intK){intnflavor.size();if(Kn)return0;// 段数超过元素数无法切// 第 1 步预处理 distinct[l][r] // distinct[l][r] flavor[l..r] 中不同元素的个数vectorvectorintdistinct(n,vectorint(n,0));for(intl0;ln;l){unordered_setintseen;for(intrl;rn;r){seen.insert(flavor[r]);distinct[l][r]seen.size();}}// 第 2 步开 DP 表 // dp[i][j]前 i 个元素恰好切 j 段最大得分// 非法状态用 -1 表示vectorvectorintdp(n1,vectorint(K1,-1));// 第 3 步初始化 dp[0][0]0;// 前 0 个元素切 0 段得分 0唯一合法的“空”状态// j 1只切一段就是整段的不同元素数for(inti1;in;i){dp[i][1]distinct[0][i-1];}// 第 4 步按段数 j 递推 for(intj2;jK;j){// 段数从 2 到 Kfor(intij;in;i){// 前 i 个元素i j 才合法// 枚举最后一段的起点 tfor(inttj-1;ti-1;t){// 前面 t 个元素切 j-1 段必须合法if(dp[t][j-1]-1)continue;intlastSegmentScoredistinct[t][i-1];intcandidatedp[t][j-1]lastSegmentScore;if(candidatedp[i][j]){dp[i][j]candidate;}}}}returndp[n][K];}};五、循环边界为什么是这样逐条对照循环范围为什么j从 2 到 K外层j1已初始化j依赖j-1必须先算小段数i从j到 n中层前i个元素切j段必须i j否则非法t从j-1到i-1内层t j-1保证前面能切出j-1段t i-1保证最后一段非空dp[t][j-1] -1跳过转移内前面状态非法不能参与max六、用[1,2,1,2]、K2填表走一遍预处理distinctdistinct[0..3][0..3]: r0 r1 r2 r3 l0: 1 2 2 2 l1: - 1 2 2 l2: - - 1 2 l3: - - - 1初始化j1dp[0][0] 0 dp[1][1] distinct[0][0] 1 dp[2][1] distinct[0][1] 2 dp[3][1] distinct[0][2] 2 dp[4][1] distinct[0][3] 2j2i从 2 到 4i2t从 1 到 1t1dp[1][1] distinct[1][1] 1 1 2→dp[2][2] 2i3t从 1 到 2t1dp[1][1] distinct[1][2] 1 2 3t2dp[2][1] distinct[2][2] 2 1 3dp[3][2] 3i4t从 1 到 3t1dp[1][1] distinct[1][3] 1 2 3t2dp[2][1] distinct[2][3] 2 2 4✅t3dp[3][1] distinct[3][3] 2 1 3dp[4][2] 4最终表j0 j1 j2 i0 [ 0 -1 -1 ] i1 [ -1 1 -1 ] i2 [ -1 2 2 ] i3 [ -1 2 3 ] i4 [ -1 2 4 ] ← 答案答案dp[4][2] 4对应切法[1,2] | [1,2]得分224。✅七、几个容易写错的点自查清单dp表大小是(n1) × (K1)不是n × K。因为“前 0 个元素”也是一个状态。非法状态用-1标记转移时跳过避免-1 分数污染max。i从j开始不是从1开始否则会算出“前 1 个元素切 2 段”这种非法状态。t从j-1开始不是从0开始否则前面t个元素不够切j-1段。dp[i][1]的初始化用distinct[0][i-1]注意右端是i-1不是i。八、一句话记住这个 DPdp[i][j] 前i个元素切j段的最大分转移就是枚举“最后一段从t开始”把“前t个切j-1段的最优”加上“最后一段自己的不同口味数”取最大。表是(n1)×(K1)只有i j的格子合法答案是右下角。