【题目来源】学而思编程最小消耗【题目描述】有n nn个怪兽等待你去消灭。怪兽共分为两种形态不妨用0 00和1 11来表示。消灭一个0 00形态的怪兽需要耗费的法力值为a aa。消灭一个1 11形态的怪兽需要耗费的法力值为b bb。你还可以使用改造魔法将0 00形态怪兽改造为1 11形态或将1 11形态怪兽改造为0 00形态。改造一个怪兽需要耗费的法力值为c cc。请问将怪兽全部消灭最少需要耗费多少法力值。【输入】第一行包含整数T TT表示共有T TT组测试数据。每组数据第一行包含四个整数n , a , b , c n,a,b,cn,a,b,c。第二行包含一个长度为n nn的01 0101字符串其中的第i ii个字符表示第i ii个怪兽的初始形态。【输出】每组数据结果占一行输出一个整数表示最小消耗【输入样例】3 4 1 2 1 1001 6 1 1 1 101011 3 2 1 3 111【输出样例】6 6 3【核心思想】问题分析给定n nn个怪兽每个怪兽有形态0 00或1 11。消灭形态0 00消耗a aa消灭形态1 11消耗b bb改造一个怪兽消耗c cc。求消灭所有怪兽的最小总消耗。这是一个贪心决策问题关键在于对每个怪兽独立决策直接消灭还是改造后再消灭。算法选择独立贪心每个怪兽的处理方式相互独立分别计算两种形态的最优处理成本最小值选择对于每个怪兽比较直接消灭和改造后消灭两种方案取较小值关键步骤初始化读取T TT测试组数处理每组数据读取n , a , b , c n, a, b, cn,a,b,c和形态字符串s ss计算单怪兽最优成本kill0 min(a, b c)形态0 00的怪兽直接消灭成本a aa或改造成1 11再消灭成本b c b cbc取较小值kill1 min(b, a c)形态1 11的怪兽直接消灭成本b bb或改造成0 00再消灭成本a c a cac取较小值累加总成本ans 0遍历i ii从0 00到n − 1 n-1n−1若s[i] 0ans kill0否则ans kill1输出ans时间/空间复杂度时间复杂度O ( T × n ) O(T \times n)O(T×n)每组数据线性遍历字符串空间复杂度O ( n ) O(n)O(n)存储形态字符串独立贪心决策的核心思想怪兽间独立性每个怪兽的改造和消灭决策不影响其他怪兽总成本为各怪兽成本之和无耦合约束单怪兽最优即全局最优由于无跨怪兽约束每个怪兽取自身最小成本即可保证全局最小两种策略对比对每个怪兽只有两种选择直接消灭当前形态 / 改造成另一形态再消灭m i n minmin操作覆盖所有可能改造的双向性0 → 1 0 \to 10→1和1 → 0 1 \to 01→0的改造成本相同均为c cc但改造后的消灭成本不同需分别计算适用于独立个体 二元选择类问题贪心策略将组合优化简化为每个元素的独立决策【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;intT;string s;intmain(){cinT;// 读取测试用例数量while(T--)// 处理每个测试用例{intn,a,b,c;cinnabcs;// 读取n, a, b, c和字符串sintkill0min(a,bc);// 处理字符0的最小花费intkill1min(b,ac);// 处理字符1的最小花费intans0;// 总花费for(inti0;in-1;i)// 遍历字符串s{if(s[i]0)// 如果字符是0{anskill0;// 加上处理0的最小花费}else// 如果字符是1{anskill1;// 加上处理1的最小花费}}coutansendl;// 输出总花费}return0;}【运行结果】3 4 1 2 1 1001 6 6 1 1 1 101011 6 3 2 1 3 111 3
题解：学而思编程 最小消耗
发布时间：2026/7/5 15:14:46
【题目来源】学而思编程最小消耗【题目描述】有n nn个怪兽等待你去消灭。怪兽共分为两种形态不妨用0 00和1 11来表示。消灭一个0 00形态的怪兽需要耗费的法力值为a aa。消灭一个1 11形态的怪兽需要耗费的法力值为b bb。你还可以使用改造魔法将0 00形态怪兽改造为1 11形态或将1 11形态怪兽改造为0 00形态。改造一个怪兽需要耗费的法力值为c cc。请问将怪兽全部消灭最少需要耗费多少法力值。【输入】第一行包含整数T TT表示共有T TT组测试数据。每组数据第一行包含四个整数n , a , b , c n,a,b,cn,a,b,c。第二行包含一个长度为n nn的01 0101字符串其中的第i ii个字符表示第i ii个怪兽的初始形态。【输出】每组数据结果占一行输出一个整数表示最小消耗【输入样例】3 4 1 2 1 1001 6 1 1 1 101011 3 2 1 3 111【输出样例】6 6 3【核心思想】问题分析给定n nn个怪兽每个怪兽有形态0 00或1 11。消灭形态0 00消耗a aa消灭形态1 11消耗b bb改造一个怪兽消耗c cc。求消灭所有怪兽的最小总消耗。这是一个贪心决策问题关键在于对每个怪兽独立决策直接消灭还是改造后再消灭。算法选择独立贪心每个怪兽的处理方式相互独立分别计算两种形态的最优处理成本最小值选择对于每个怪兽比较直接消灭和改造后消灭两种方案取较小值关键步骤初始化读取T TT测试组数处理每组数据读取n , a , b , c n, a, b, cn,a,b,c和形态字符串s ss计算单怪兽最优成本kill0 min(a, b c)形态0 00的怪兽直接消灭成本a aa或改造成1 11再消灭成本b c b cbc取较小值kill1 min(b, a c)形态1 11的怪兽直接消灭成本b bb或改造成0 00再消灭成本a c a cac取较小值累加总成本ans 0遍历i ii从0 00到n − 1 n-1n−1若s[i] 0ans kill0否则ans kill1输出ans时间/空间复杂度时间复杂度O ( T × n ) O(T \times n)O(T×n)每组数据线性遍历字符串空间复杂度O ( n ) O(n)O(n)存储形态字符串独立贪心决策的核心思想怪兽间独立性每个怪兽的改造和消灭决策不影响其他怪兽总成本为各怪兽成本之和无耦合约束单怪兽最优即全局最优由于无跨怪兽约束每个怪兽取自身最小成本即可保证全局最小两种策略对比对每个怪兽只有两种选择直接消灭当前形态 / 改造成另一形态再消灭m i n minmin操作覆盖所有可能改造的双向性0 → 1 0 \to 10→1和1 → 0 1 \to 01→0的改造成本相同均为c cc但改造后的消灭成本不同需分别计算适用于独立个体 二元选择类问题贪心策略将组合优化简化为每个元素的独立决策【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;intT;string s;intmain(){cinT;// 读取测试用例数量while(T--)// 处理每个测试用例{intn,a,b,c;cinnabcs;// 读取n, a, b, c和字符串sintkill0min(a,bc);// 处理字符0的最小花费intkill1min(b,ac);// 处理字符1的最小花费intans0;// 总花费for(inti0;in-1;i)// 遍历字符串s{if(s[i]0)// 如果字符是0{anskill0;// 加上处理0的最小花费}else// 如果字符是1{anskill1;// 加上处理1的最小花费}}coutansendl;// 输出总花费}return0;}【运行结果】3 4 1 2 1 1001 6 6 1 1 1 101011 6 3 2 1 3 111 3
