终于50题，继续努力

Consider the partial sum sequence of each of the k features built by taking the 


sum of all the values up to position i. The problem is equivalent to:

Given an array s[n][k], find i,j, with the biggest separation for which s[ i ]


[l]-s[j][l] is constant for all l. 

The problem is now to do this efficiently. Notice that s[ i ][l]-s[j][l] being 


constant for all l is equivalent to s[ i ][l]-s[j][l]=s[ i ][1]-s[j][1] for all 


l, which can be rearranged to become s[ i ][l]-s[ i ][1]=s[j][l]-s[j][1] for all 


l. Therefore, we can construct another array a[n][k] where a[ i ][j]=s[ i ][j]-


s[ i ][1] and the goal is to find i and j with the biggest separation for which 


a[ i ][l]=a[j][l] for all l. 

This can be done by sorting all the a[ i ] entries, which takes O(nklogn) time 


(although in practice rarely will all k elements be compared). Another 


alternative is to go by hashing, giving an O(nk) solution. Both solutions are 


fairly straightforward once the final array is constructed.

• 原来如此!! THX (3) DE_SEAN 2010-12-15 00:00:15
• thx 开始动手 (0) ycdoit 2011-04-04 22:01:04
• Re:poj 50题纪念附官方解题报告：疑问 (164) 15914304086 2012-07-14 08:27:32
  • Re:poj 50题纪念附官方解题报告：疑问:请问怎么个增加法？ (18) 771385494 2012-07-18 15:39:55