2015年5月2日土曜日

Hacker Rank : Wet Shark and Two Subsequences

問題

https://www.hackerrank.com/challenges/wet-shark-and-two-subsequences
n項の数列{x_i}とrとsが与えられるので、
以下の条件を満たす数列の部分集合A,Bがいくつ存在するかを求める問題
・|A|=|B|
・sum(A)+sum(B)=r
・sum(A)-sum(B)=s

解法

sum(A)=(r+s)/2
sum(B)=(r-s)/2
となるのでdp[i][j][k]=i番目までの和がjとなるようなサイズkの部分列の個数
してdp.

0 件のコメント:

コメントを投稿