【No.018】「 AOJ-ICPC 550 引っ越し」

この問題を解くためには、

元の数列の総和から、「その数列から任意の長さの部分増加列を取り出して、その増加部分列の要素の総和を最大化したときの値」を引けばよいです。

サンプル1ならば、

元の数列 : { 1, 4, 2, 3 }

元の数列の総和 = 1+4+2+3 = 10

総和が最大の増加部分列 : { 1, 2, 3 }

増加部分列の総和 = 1+2+3 = 6

よって、10-6=4が答えになります。

※要するに増加部分列に採用されなかった項は、体力を消費して動かすことになる。

サンプル4ならば、

元の数列 : { 6, 2, 1, 3, 8, 5, 4, 7 }

元の数列の総和 = 6+2+1+3+8+5+4+7 = 36

総和が最大の増加部分列 : { 2 , 3 , 5 , 7 }

増加部分列の総和 = 2 + 3 + 5 + 7 = 17

答え = 36 - 17 = 19

総和が最大になる増加部分列を求める問題をO( n^2 )で解く場合、どの項に着目しているかを状態に持って、次にどこの項を採用するかで遷移するDPになります。

このとき、遷移にO(N)かかってしまうところを、セグメントツリーやBITをつかうことでO( log N ) で遷移できるようになります。

dohatsutsu’s diary