acm题目求算法知道XXXhasanarrayoflengthn.XXXwantstoknowthat,foragivenw,whatisthesumofthedistinctelements’numberinallsubstringsoflengthw.Forexample,thearrayis{1123445}Whenw=3,therearefivesubstrings

Question

acm题目求算法知道
XXX has an array of length n.XXX wants to know that,for a given w,what is the sum of the distinct elements’ number in all substrings of length w.For example,the array is { 1 1 2 3 4 4 5 } When w = 3,there are five substrings of length 3.They are (1,1,2),(1,2,3),(2,3,4),(3,4,4),(4,4,5)
The distinct elements’ number of those five substrings are 2,3,3,2,2.
So the sum of the distinct elements’ number should be 2+3+3+2+2 = 12.
Input
There are several test cases.
Each test case starts with a positive integer n,the array length.The next line consists of n integers a1,a2…an,representing the elements of the array.
Then there is a line with an integer Q,the number of queries.At last Q lines follow,each contains one integer w,the substring length of query.The input data ends with EOF For all cases,0

Answer 1

这题不容易想到,一看题目,看到这数据范围,看到查询的方式.一直在往树状数组或者线段树方面去想.
想到了用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了.
你可以追问,我把代码贴出来