ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

JOI 2012 予選 D 暑い日々

JOI 2012-2013 予選 問題4
提出コード
動的計画法を使うことを考えます。
まず、dp[i][j]として、j日目にi番目の服を着たときの、1~j日までの、「派手さの差の絶対値」の合計の最大値、とすると、

  • dp[i][j]=max(dp[k][j-1]+k番目の服とj番目の服の差の絶対値)

となります(ここで、kはj-1日目に着ることができる服の中から任意に選んだ番号です)。
ですが、よく考えてみると、j-1日目に来た服に対して一番絶対値が大きくなるようなj日目の服は、

  • j日目に着ることができる服のうち、派手さが最大か最小であるもの

の2種類のどちらかでしかないので、計算量をさらに減らすことができます(具体的には、dp[i][j]のiを、2種類に減らすことができます)
あとは、入力の段階である温度に対して着ることができる服の最大値と最小値を求め、それをもとに動的計画法を適用すれば答えが求まります。
答えはdp[i][d]の最大値になります。

やり残した問題がだいたい片付いたので、けんちょんさんのブログの、蟻本の類題をといていく日々が始まりそうです。