.LetX={1,2,3,4,5}.ConsiderthesetVofalltwoelements

来源：蜘蛛抓取(WebSpider) 时间：2019-09-18 09:49 标签： X.
这题不容易想到,一看题目,看到这數据范围,看到查询的方式.一直在往树状数组或者线段树方面去想.

想到了用DP解决就不难了.用DP的思路O(n)复杂度解决.以样例为例说明：1 1 2 3 4 4 5；明显dp[1]=n=7;长度為1的时候有7个区间.从长度为1到长度为2,就是把前6个区间往后增加一个数,把最后一个区间去掉.增加的6个数要看在该区间是否出现过,只要看它上┅个相等的元素距离是否大于2（这里有四个大于2,而1个小于,就是1,1）所以dp[2]=dp[1]-1+4;以此类推就可以得出所以的dp值了.dp[i]=dp[i-1]-A+B;减的A是最后一个长度为i-1的区间的不同數的个数,这个很容易预处理得出来.加的B是第t个数到它上一个数的距离大于i-1的个数.这个B值也容易得出.用s[i]表示离上一个数的距离为i的个数,不断減掉就得到B了.你可以追问,我把代码贴出来

免费查看千万试题教辅资源

这题不容易想到,一看题目,看到这數据范围,看到查询的方式.一直在往树状数组或者线段树方面去想.

想到了用DP解决就不难了.用DP的思路O(n)复杂度解决.以样例为例说明：1 1 2 3 4 4 5；明显dp[1]=n=7;长度為1的时候有7个区间.从长度为1到长度为2,就是把前6个区间往后增加一个数,把最后一个区间去掉.增加的6个数要看在该区间是否出现过,只要看它上┅个相等的元素距离是否大于2（这里有四个大于2,而1个小于,就是1,1）所以dp[2]=dp[1]-1+4;以此类推就可以得出所以的dp值了.dp[i]=dp[i-1]-A+B;减的A是最后一个长度为i-1的区间的不同數的个数,这个很容易预处理得出来.加的B是第t个数到它上一个数的距离大于i-1的个数.这个B值也容易得出.用s[i]表示离上一个数的距离为i的个数,不断減掉就得到B了.你可以追问,我把代码贴出来

免费查看千万试题教辅资源

我要回帖

更多关于 X. 的文章

 

随机推荐