NOIP集训-10.20总结

YYY posted @ 2015年10月20日 15:52 in OI相关 with tags 贪心最短路径倍增 , 543 阅读

_THIS_IS_START_OF_ARTICLE_

水啊水..

-------------------------------------------------------------------

math:SuperOjP941

贪心，已乘积和最大为例。

首先把a排序，然后就只需考虑b的排列

假设b中有一个逆序对(i,j)，易证交换(i,j)后比原来更优

因此b中一定没有逆序对，即升序排好了序

乘积最小同理易证

-------------------------------------------------------------------

tree:SuperOjP942

SB 倍增...

-------------------------------------------------------------------

shortest:SuperOj943

考虑从右往左加点

每加入一个点，考虑更新这个点以及其他点的最短路径

考虑floyd算法

但是发现需要改变的点一定是和当前加入的点有关的

因此有一层循环就已经固定下来了

因此就只有两层循环，n^2

统计答案就暴力统计，也是n^2

因此总的复杂度就是O(n^3)的

-------------------------------------------------------------------

_THIS_IS_END_OF_ARTICLE_

YYY