贪心 邻项交换 数学

进一步学习:

1.具体数学
2.离散数学
3.布尔代数
4.Matroid
5.(逻辑学)

你需要学会的技能:

解最值不等式

严格弱序

  1. It has to be antisymmetric. This means that for operator <: If x<y is true, then y<x is false. This means that for a predicate op(): If op(x,y) is true, then op(y,x) is false.
  2. It has to be transitive. This means that for operator <: If x<y is true and y<z is true, then x<z is true. This means that for a predicate op(): If op(x,y) is true and op(y,z) is true, then op(x,z)is true.
  3. It has to be irreflexive. This means that for operator <: x<x is always false. This means that for a predicate op(): op(x,x) is always false.
  4. It has to have transitivity of equivalence, which means roughly: If a is equivalent to b and b is equivalent to c, then a is equivalent to c. This means that for operator <: If !(a<b)&&!(b<a) is true and !(b<c)&&!(c<b) is true.then !(a<c)&&!(c<a) is true. This means that for a predicate op(): If op(a,b), op(b,a), op(b,c), and op(c,b) all yield.false, then op(a,c) and op(c,a) yield false.
    STL库要求重载的'<' 运算符满足严格弱序,否则出现未定义的行为。

可用于贪心的结论

定义二元布尔关系A\odot B:=\min(A.x,B.y)<\min(A.y,B.x)
可以证明\forall A\odot B 且 B\odot C,有A\odot C

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,424评论 0 10
  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,811评论 0 23
  • Lua 5.1 参考手册 by Roberto Ierusalimschy, Luiz Henrique de F...
    苏黎九歌阅读 13,878评论 0 38
  • 小时候,爸爸总带我去看树, 告诉我每棵树的名字。 包括他的小名和各种别名。 讲述着他和树的故事。 他耐心讲了无数次...
    梦游的柔儿阅读 124评论 0 0
  • 某君特别爱笑,见人不笑不说话。 有人打他、骂他,他更是狂笑不止。不理解他的人骂他是疯子,也有崇拜他的人...
    AL阿林阅读 862评论 11 12