usaco题目“田忌赛马”
题目
usaco题目“田忌赛马”
这道题目我第一次看到想到的是邻接表+二分图.但是我不会二分图最佳匹配,网络流也不太熟练.于是想到先求一次赢的最大匹配,再从剩余的马中求一次平的最大匹配.这样来求解对么?不对的话请给出一个反例谢谢.我只想知道对不对,为什么.发代码和建议我用其他方法的一律不采纳.
答案
这样是对的
设一个方案P中.共有W场,赢了N场,平了K场,则输了(W-N-K)场
那么该方案赢得的钱数为200N-200(W-N-K)=400N+200K-200W
因-200W一定..该题就是求最大的400N+200K
现在证明对于N最大,且在N最大的情况下K最大的方案P1,其赢得的钱设为T1,对任意方案Pi,T1>=Ti
1)对于方案Pi,如果Ni=N1,则Ki
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点
- 人民路小学六年级上学期有学生360人,其中男生占十二分之七,本学期又转来若干名男生,这样男生人数占
- 已知3的m次方=5,求（1）3的3m次方的值；（2）3的3m+2的值
- 1、为什么气焊点火时先开乙炔阀；2、为什么发生回火时应迅速关闭氧气阀；3、为什么氧气管着火时先关闭氧气
- 若某二次函数当自变量x等于二时,函数值y有最大值-1,则这样的二次函数可以是 （任意写一个）
- 一道高数题,设y=ln【f（x）】,其中f’’（x）存在,求(d^2y)/(dx^2) ,
- 梅以它的高洁、坚强、谦虚的品格,给人以立志奋发的 激励.在严寒中,梅开百花之先,独天下而春,因此梅
- 求关于friendship的英语演讲稿
- 填空题：原子核外电子的排布有一定的规律：（1）各电子层最多容纳的电子数是多少个?（2）最外尾电子数不超过多少个?（K层为最外层时不超过多少个?）,（3）次外层的电子数不超过多少个?（4）倒数第三层电子
- difficult very ill problem student的近义词
- 关于x的一元二次方程（1-m）x+（m+2）x-1=0的解的情况是什么