这个一看真的不知道是个啥
观察可知，如果想要处理第i位上的元素使之有序必须要把前i-1位全部变成有序。我们再分开来想
如果第i位是i，多移动0步
第i位是1，多移动1步
第i位是2，多移动2步：把2提前再把1提前。
第i位是3多移动4步：把3提前，重复之前两步
也就是说，最后一位是i,移动2^(i-1)步
因此，把前i为變成有序要走(i-1某种情况的步数)+2^(最后一位是啥)。我们合起来考虑对于前i-1位同一种情况，最后一位多移动的值加和是(2^i-1)而前i-1位共有!(i-1)种情况，所以f[i]=f[i-1]i+(2^i-1) !(i-1)递推就好了。
说实在考试时真的没想到，就交上去了一个dfs可能因为T2耗的时间太长了，心里有点发慌没有真的静下心去想。栲试心态有待提高

发布了212 篇原创文章 · 获赞 5 · 访问量 5万+