問題概要
問題文はこちらを参照してください。
苦手なタイプの問題です。
解法
ＤＰは前提だとして考えると、部分問題を設定しないといけません。$i-1$番目までの猫で得られる幸福度の総和がわかっているとします。そこに、$i$番目の猫を加えたときに増える幸福度は、猫$i$がすでにいた猫のうち、どの猫と距離1以内なのかによります。$j$番目の猫までと距離1以内とすると、$j\le i$という条件で、$j,j+1,...,i-1,i$番目までの猫もすべて距離1以内になるはずです(自分自身も含めています)。なので、猫$i$の幸福度は$\displaystyle \sum_{l=j}^{i}f_{i,l}$となり、すでにいた$j～i-1$までの猫の幸福度がそれぞれ猫$i$との仲のよさ分増えるので、結局猫$i$の幸福度の分の2倍、$\displaystyle 2\cdot\sum_{l=j}^{i}f_{i,l}$増えることになります。
ここで出てきた、すでにいる猫の(左側の)どこまで距離1以内なのかという条件を付けて部分問題を考えると、猫$i$は猫$j$までが距離が1以内とすると、猫$i$よりも左にいる猫$i-1$は、必ず、猫$j$かそれよりも左にいる猫まで距離1以内のはずです。
なので、猫$i-1$が$j,j-1,...,1$番目の猫まで距離1以内の時の幸福度の最大値に、$i$番目の猫を加えたときに増える幸福度を足して最大になるような幸福度の総和を求めればよいことになります。
配列でイメージを示すと以下のようになります。
$dp[i][j]$：$i$番目までの猫で、猫$i$から猫$j$までが距離1以内のときの幸福度の総和の最大値。($j=i$の時は猫$i$を加えても全体の幸福度は増えないので$i-1$番目までの猫での幸福度の最大値と同じ)
$f_{i,j}$：猫$i$と猫$j$の仲のよさ。
$(1\le i \le n,\ 1\le j\le i)$
初期値：$dp[1][1]=0$
求める解：$2\cdot dp[n][j]$の最大値$(1\le j\le n)$
漸化式の中で、$k$と$l$は別にループが回せるので、これで$O(n^3)$になり、このままではまだ駄目です。
図の中の1)の部分ですが、$l$を$i$から$j$の方向に累積和を考えることで、$\displaystyle sum[i][j]=\sum_{l=j}^{i}f_{i,l}$という$sum[i][j]$を$O(n^2)$で事前に計算することができます。
図の中の2)の部分ですが、$dp[i][j]$を猫$i$からの距離が1以内の猫が、猫$j$かそれよりも左の場合の幸福度の最大値、つまり上記の漸化式で$dp[i-1][j]=\max\{dp[i-1][k]:k=1,2,...,j\}$と定義しなおすと、$dp[i][j]=\max\{dp[i][j-1], dp[i-1][j]+sum[i][j]\}(j=1,2,...)$と更新していくことで、$k$のループを回す必要がなくなります。
これらを踏まえて漸化式を書き直すと$O(n^2)$で解けます。
$dp[i][j]$：$i$番目までの猫で、猫$i$から猫$1$～猫$j$のどれかまでが距離1以内のときの幸福度の総和の最大値。
$sum[i][j]$：猫$i$が猫$j$から自分自身までが距離１以内の時の猫$i$の幸福度。
$(1\le i \le n,\ 1\le j\le i)$
初期値：$dp[1][1]=0$、$dp[i][0]=-INF(1\le i \le n)$(適切な小さな値)
求める解：$2\cdot dp[n][n]$
猫$i$が加わることによって増える全体の幸福度の総和は、猫$i$の幸福度の2倍なのですが、ＤＰの時は2倍せずに最後の解のところで2倍するようにしています。
初期値の$-INF$ですが、最小の仲のよさの最小値が$-1000$、猫が1000匹までなので1匹の幸福度の最小値が$-10^6$、1000匹の総和で$-10^9$までなりそうです。したがって、$-INF$はこれよりも小さい値でなければいけません。
考察
図中の1)の累積和のオーダーを落とすところはわかるような気がするのですが、2)のオーダーの落とし方が結構苦手です。最初解いたとき(解説見た後に)は$O(n^3)$でもACだったのですが、いろいろな解説を見ると$O(n^2)$だということで、この投稿を書く中で何とか理解したつもりです。
コメント