読者です 読者をやめる 読者になる 読者になる

dohatsutsu’s diary

日記を書いています。

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

House Moving | Aizu Online Judge

 

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

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

 

サンプル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 ) で遷移できるようになります。