其他回答

• http://acm.hdu.edu.cn/forum/里面很多资料，自己下吧各大OJ会收录比赛题目，解析就去找解题报告，自己搜吧。
  连亚臣2019-12-21 18:55:35
• 有N个石子,每个石子重量Qi；按顺序将它们装进K个筐中；求一种方案，使得最重的筐最轻。分析：本题乍一看很容易想到动态规划。事实上的确可以用动态规划解决，稍加分析我们很快得到一个简单的算法。用状态fi,k表示将前i个石子装入k个筐最优方案，gi,j表示i-j中最重的石子，则可以写出状态转移方程：gi,j=max{gi,j-1,Qj}fi,j=minmax{fk,j-1,gk+1,i}|1k，则找到权值最大的中点，删去其后的数。这个简化后的问题可以直接扫描，开始时为一个长度为K的段，设为Q1,Q2,…Qk，每次添加一个新数，若Q1+Q2+..+QL-K小于0，则把它们从数列中删去，不断更新最优解即可。这样我们就能在ON的时间内找到长度不小于k且和最大的连续段。之所以能成功解决简化后的问题，是由于该问题中每个量对最终结果的影响是确定的，若其小于0，则对结果产生不好的影响，反之则是有益的影响。那么原问题每个参数对最终结果的影响是不是确定的呢？很遗憾，并不是这样，因为每个题目有两个不同的参数，他们之间存在着某些的联系，而这些联系又具有不确定性，故我们很难知道它们对最终结果是否有帮助。想解决原问题，必须设法消除这个不确定因素！那么有没有办法将这些不确定的因素转化成确定的因素呢？此时，引入参数势在必行！那么我们引入参数P，求一个新的问题：找一个比值不小于P的方案。这个问题实际就是求两个下标i’,j’，满足下面两个不等式j’-i’+1≥k①Ai’+Ai’+1....+Aj’/Bi’+Bi’+1…+Bj’≥p②由不等式②=>Ai’+Ai’+1....+Aj’≥pBi’+Bi’+1…+Bj’整理得Ai’-pBi’+Ai’+1-pBi’+1…+Aj’-pBj’≥0可以令Ci=Ai-pBi，则根据上面不等式可知问题实际求一个长度不小于k且和大于０的连续段。由之前的分析可以知道我们能在ON的时间内求出长度不小于k且和最大的连续段，那么如果该段的和大于等于０，则我们找到了一个可行解，如果和小于０，则问题无解。也就是说，我们已经能在ON的时间内判断出是否存在比值不小于P的方案，那么接下来的步骤也就顺理成章了。我们需要通过二分法调整参数P，不断逼近最优解。计算一下以上算法的时间复杂度，设答案为T，则该算法的时间复杂度为ONlgT，虽然这并不是多项式级别的算法，但在实际使用中的效果非常好。　引入参数后，由于增加了一个条件，我们就可以将不确定的量变为确定的量，从而解决了问题。三．总结本文主要通过几个例子说明了参数搜索法在信息学中的应用，从上文的例子可以看出加入参数一方面能大大降低思维复杂度，另一方面也能得到效率相当高的算法，这使得我们解最解问题又多了一中有力的武器。当然，任何事物都是具有两面性的。参数搜索在具有多种优点的同时也有着消极的一面。由于需要不断调整参数逼近最优解，其时间复杂度往往略高于最优算法，且通常依赖于某个权值的大小，使得我们得到的有时不是严格意义上的多项式算法。文章中还总结了使用此方法解题的一般步骤，在实际应用中，我们不能拘泥于形式化的东西，必须灵活应用，大胆创新，这样才能游刃有余的解决问题。
  黄白红2019-12-21 18:39:09