usaco题目“田忌赛马”
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/07/06 20:46:56
usaco题目“田忌赛马”
这道题目我第一次看到想到的是邻接表+二分图.但是我不会二分图最佳匹配,网络流也不太熟练.于是想到先求一次赢的最大匹配,再从剩余的马中求一次平的最大匹配.这样来求解对么?不对的话请给出一个反例谢谢.我只想知道对不对,为什么.发代码和建议我用其他方法的一律不采纳.
这道题目我第一次看到想到的是邻接表+二分图.但是我不会二分图最佳匹配,网络流也不太熟练.于是想到先求一次赢的最大匹配,再从剩余的马中求一次平的最大匹配.这样来求解对么?不对的话请给出一个反例谢谢.我只想知道对不对,为什么.发代码和建议我用其他方法的一律不采纳.
![usaco题目“田忌赛马”](/uploads/image/z/19533728-56-8.jpg?t=usaco%E9%A2%98%E7%9B%AE%E2%80%9C%E7%94%B0%E5%BF%8C%E8%B5%9B%E9%A9%AC%E2%80%9D)
这样是对的
设一个方案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
设一个方案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