HBC25153区间异或,枚举,位运算[USACO 2006 Oct S]Fence Repair题解

你曾走过我的故事算法基础篇 2023-11-26 09:59:01 98 0

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

农民 John 希望修复围绕农场的一小段围栏，他测量了一下，发现需要N (1

农民 John 希望修复围绕农场的一小段围栏。他测量了一下，发现需要N (1 <= N <= 20,000) 根木头，每根都有某一个整数长度 Li (1 <= Li <= 50,000) 单位长度。他买了一根很长的很长的木头，正好能够锯出他所需要的N根木头。(即它的长度正好等于Li的总和) FJ 忽略锯口，锯掉的木屑产生的长度损失忽略不计，你也可以忽略它。 FJ 遗憾的发现他自己没有用于切木头的锯子，所以他就带着那根很长的木头来到了农民 Don的农场，想问他借一个锯子。农民 Don是一个保守的资本家，他不愿意借锯子给 FJ ，但愿意自己来切这N-1刀，每一次都向FJ收取费用。每次的收费正好等于你要锯的那根木头的总长度。例如，你要锯一根长度为21的木头，就花费21分钱。农民 Don 然后让农民 John 自己决定每次锯木头的顺序和位置。帮助农民 John 确定锯出这N根木头的最小总花费。 FJ 知道可以有很多种不同的切割方式，不同的方式可能得到不同的总花费，这是因为木头在锯的过程中的长度不一。