一行超人

既然不是历年的省选题那么就来写一下题解吧

A.序列操作 

题意：给一个n个数的数列，每次可以交换相邻两个数。问最少多少次可以把整个序列变成不降的。n<=10^5

题解：这水题。。。还不及NOIP2013day1T2。。。裸树状数组

      下来爆零就搞笑了

B.交错匹配

题意：给出a[n]和b[m]分别表示写在上面的一行数和下面的一行数其中每个元素都<=32767。

      然后加入a[i]=b[j]=K，那么就可以在i和j之间连一条边，并称其为一个K匹配。现在要求一个K匹配必须（jin）和一个L匹配相交并且

      K!=L。问最大匹配数。n，m<=1000

题解：我们令f[i][j]表示a用了前i个，b用了前j个的最大匹配数。

      那么DP的时候我们有三种情况

      1）强制i和j都作为一个选了的匹配，那么如果a[i]=b[j]是不行的，否则不妨认为l为b[j]在a中上一次出现的位置，

         r为a[i]在b中上一次出现的位置，那么可以用f[l-1][r-1]+2来更新f[i][j]。

      2）不选a[i], f[i][j]=max(f[i][j],f[i-1][j])

      3）不选b[j]，f[i][j]=max(f[i][j],f[i][j-1])

      正确性显然，复杂度O（n*m）。

      这道题事（zuo）后（wan）知道解法的时候感觉并不是什么神题，但是感觉为什么这样一种题出现在省选中就团灭了我们呢。。。

     UPD： Tunix大神在看错题的情况下凭自己超高的OI水平想出了正解！让我们一起献上膝盖吧！！！

      我认为这一题主要用了一种构造的思路，因为如果我们确定了一个交错匹配的后两个位置是什么，一定能确定较优的前两个位置，这样就直接使问题迎刃而解了。

      另一方面可能还是因为我们对于DP的理解还不够，我考场写的就太傻逼了。在确立了状态之后应该利用这个状态应该好好想一下怎么用状态的表示来简化问题，一步一步的递推的思路应该好好体会，例如上面的分情况讨论。而不是无脑的枚举前继状态。而且DP的状态也要设计好。总之还是构造的思路比较巧妙，我的智商不太够用。

       当然主要原因还是我们太弱了我们太弱了我们太弱了我们太弱了我们太弱了我们太弱了我们太弱了

C.过路费

题意：n个点，m条双向边，每条边有个过路费，每个城市也有一个过路费。定义一条路径的花费为边的过路费之和+（途经城市的过路费的最大值）。给出Q个询问，问你s到t的最小花费。n<=250 m<=1W Q<=1W

题解：首先一维的spfa不论保证城市过路费最小还是边的过路费之和最小还是两者之和最小都是无法保证全局的最优性的，换句话说这个DP不满足子问题最优性质。二维spfa，dp[i][j]表示到i城市最大过路费为j的最短路径是正确的，但是复杂度O（n^2*m），可能会TLE。

      所以问题的棘手就在于途经城市的过路费是按最大来收的。

      其实这种问题的处理方法已经出现过好多次了。   

      我们考虑在floyed过程中最外层的k循环表示的意义，假设k循环到了 l，那么f[i][j]表示的就是i到j只经过编号<l的中间点的最短路径。那么我们就可以让k从过路费从小到大循环，那么这时的这条路径的花费就一定是f[i][k]+f[k][j]+w[k]。f[i][j]还是表示最短路。

      ans[i][j]=min(ans[i][j],f[i][k]+f[k][j]+w[k]）。

      当然要处理一些细节问题。

      有人问我这题的从小到大加进去的思路是怎么想到的？我这么弱怎么可能自己想到，肯定是被这类型的题目坑了好多次一次都没想出来这次才机智了一下。

      这里就把我见过的有用到这中思路的一些题目都列出来：

      矩阵乘法  随机数生成器  魔法森林 爱的经验 爱的距离  后面这俩题的题目。。。【捂脸熊】

      下来爆零就搞笑了

D.长方形

题意：一个n*m的01矩阵，问你有多少种方案可以选出一个全是1的长方形。n,m<=1000

题解：单调栈搞一搞，分行搞。

      h[i]表示i这一列向上有多少个1。

      我们考虑计算以每个点为右下角合法的左上角的方案数g[i]。

      那么不妨令f[i]表示h[i]作为最小值向左最远能拓展到哪里。

      那么g[i]=g[f[i]]+(i-f[i])*h[i] 正确性显然。然后累加答案即可。

      下来爆零就搞笑了