运行时限：2sec内存限制：1024MB原题链接AtCoderBeginnerContest104C代码竞赛平台AtCoder为您提供全面的算法选择。AlgorithmsComprehensiveAnthologyEncyclopedia包含多个问题选集。每个问题选择根据其难度给予相应的分数。现在有一个整数i，1<=i<=D，D是一个具体的整数。问题选择编号为i。对于编号为i的题集中的问题，每解决一道题，给出100*i的分数。我们给定的算法综合选集百科全书涵盖了编号为1,2,3...D的问题选集。对于编号为i的问题集，其中有Pi题，如果解决了编号为i的问题集中的所有Pi题，则用户可以获得Ci的额外加分。Atcoder为每个用户分配一个综合分数。用户的综合得分有以下几部分组成基本得分：用户解决问题所获得的分数的总和。小明的目标是G以上的分数，请问小明至少要答多少题才能达到要求。输入前置条件1<=D<=101<=Pi<=100100<=Ci<=1000000100<=G所有输入都是整数Ci和G是100的倍数理论上输入选项满足要求可以达到G以上的可能input和input应该按照以下标准从命令行输入：DGp1c1..pDcD输出，请输出达到以上G分需要解决的最少题数※给定的测试请放心inputmustbeabletoreachpointsaboveGExample1Input270035005800Output3从给定的题目信息可以看出必须有2个题型选择。初选题共3题，每题100分。如果您解决所有3个问题，您可以获得500分奖励积分。第二选题共5题，每题200分。如果您解决所有5个问题，您可以获得800分奖励积分。小明的目标分数是700分。第一种能达到目的的方法，第二次选题完成5道题中的4道，得800分。第二种方法，如果你解决了第一个选择题，你可以额外获得500分，所以你也可以获得800分。第二种方法只需要解决3道题，比第一种方法成本更高。Fewexample2input2200035005800output7虽然和example1的输入很相似，但是因为目标分数是2000分，所以需要把200分的5道题都答完才能得到1800分，然后再解决2道题价值100分的题目。Example3Input240035005800Output2虽然和Example1的输入很相似，但是因为目标分数是400分，所以只需要解决200分的问题2Question4Input52500020100040100050100030100011000Output66虽然只有一题500分，但是看懂题目就可以获得完整的加分。简单来说，就是这样。共试题选集1。P2题，每题200分，全部解完，C2分加分选题3道，共P3题，每题300分，C3分加分题选题4道，共P4题，每题400分，allsolutions精选加分题C4做完题5共P5题每题500分2.但是加分制怎么办，因为有的题集给的分很低，但是他们的加分都很高，所以也要选这样的题集3.有没有这样的情况，两套题集全部完成，两套题集部分完成？答案是否定的，因为每道题的加分和加分都是不一样的。有一部分A题选集，一部分B题选集。B题选题的分数比A题选题的分数高，那何不把做A题选题的精力投入到解题集里，这样就可以获得更高的分数。从上面两张图的对比我们可以发现，将算力分配到两个选中的主题集上，总分会有所损失，因为还有另一个高分主题集，可以将算力投入到得分更高的主题集。在选定的主题集中获得更高的分数。上图显示，如果将2点算力投入到第2道题集，可以获得400基础分。如果在第2题集和第1题集上分配2点算力，只能得到300个基点。4、那么根据上面的分析，解题的可能性是N题集全部解完，至多1题集部分解题。5.1<=D<=10表示最多有10个题集，我们以完全解题集的个数为基数，所有解题集的情况有2的10次方，然后求将每种情况下得分最高的剩余问题集合作为部分解决的问题解决方案。看M中有多少题可以解出满足目标分数G的要求。1<=Pi<=100，也就是说最多允许有2的10次方*100的遍历方法时间。6、如何遍历2的10次方的情况，选择位运算7、遍历所有的情况，存储满足要求的每种情况所需解的个数。然后从这些解题次数中找出解题次数最少这里参考AtCoderContext128CSwtich(控制开关)代码S=input().split("")D=int(S[0])G=int(S[1])DATA=[]foriinrange(D):DATA.append([int(s)forsininput().split("")])defcalculate(d,_g,data):counts=[]foriinrange(2**len(data)):arr=[]bonusIndexes=[]notBonusIndexes=[]bonusSum=0bonusCounts=0forjinrange(len(data)):s=i>>j&1arr.insert(0,s)_j=len(data)-1-j如果s==1:bonusIndexes.append(_j)bonusSum=bonusSum+(_j+1)*100*data[_j][0]+data[_j][1]bonusCounts=bonusCounts+data[_j][0]else:notBonusIndexes.append(_j)g=_gifbonusSum>=g:#在这种情况下，奖金可以满足计数。append(bonusCounts)else:g=g-bonusSum#这种情况下bonus不能满足，我们要找到bonus获取不到的情况#刚需考虑当前最大单价notBonusMaxIndex=max(notBonusIndexes)notBonusMaxIndexNum=data[notBonusMaxIndex][0]notBonuxMaxIndexPrice=(notBonusMaxIndex+1)*100forninrange(1,notBonusMaxIndexNum):g=g-notCounusMaxIndexPrice=boon1ifg<=0:breakifg<=0:counts.append(bonusCounts)else:passreturncountsresult=calculate(D,G,DATA)print(min(result))总结一下，这题需要部分解这样的特征最多只有一个，然后发现D最多10个，Pi最多100个。这样可以观察到可以用遍历的方法，遍历的方法并且采取每一种可能性都是用位运算的方式※ 另外，我会在我的微信个人订阅号推出一些文章，欢迎关注
