問題概要
Alice と Bob はある歌を歌おうとしている．今，歌に表れる音階を の整数で表す（値が音の高さを表す）．また，歌おうとしている曲は配列
で表される．
Alice と Bob は一つの音は一人が歌うことにしている．また，一人の歌手にとっての難しさを，その人が歌う音を全て並べたときの，隣り合う音同士の差の絶対値の和であるとし，二人にとっての難しさを，両者の難しさの和であるとする．
二人にとっての難しさが最小になるように歌う部分を決めたときの難しさを求めよ．
解法
を
と書きます．
先頭の音から順番にどちらが歌うかを決めていくとすると， 時間かかってしまって TLE します．ところが，難しさの増分を計算する手順を考えると，二人が最後に歌った音がそれぞれ同じならば，次の音の担当を決めたときの難しさの増分は同じになることが分かります．出現する音は高々
通りなので，直前の音の組合せは，二人分でも
通りしかありません．また，音を表す値の代わりに，最後に歌った位置を覚えておけば，次に担当者を決める音の位置も分かります．つまり，次のような動的計画法を考えることができます．
- dp[ Alice が最後に歌った位置 ][ Bob が最後に歌った位置 ] := ここまでの最小の難しさ
一度も声を出していない場合をいい感じに扱うために，二つのパラメータは 1-indexed としておきます．つまり，DP テーブルは INF で埋めておいて，dp[ 0 ][ 0 ] のみ 0 をセットします．
dp[ i ][ j ] からの状態遷移は次の音をどちらが歌うかを両方試すことになります．次の音を表すインデックスである min( i, j ) を p として，
- dp[ p ][ j ] を dp[ i ][ j ] + ( i ? abs( pitch[ p ] - pitch[ i - 1 ] ) : 0 ) ) で更新
- dp[ i ][ p ] を dp[ i ][ j ] + ( j ? abs( pitch[ p ] - pitch[ j - 1 ] ) : 0 ) ) で更新
とそれぞれ更新します．
歌い終わった状態とは，どちらかが 個目の音を歌った状態です．つまり，計算が終わったあと，dp[ i ][ N ], dp[ N ][ i ] の内の最小値に答えが求まっています．
この DP の状態数は であり，状態遷移は高々定数個なので，全体では
時間で計算できます．
コード
using VI = vector< int >; using VVI = vector< vector< int > >; template < typename T = int > using LIM = numeric_limits< T >; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define SZ( v ) ( (int)( v ).size() ) constexpr int INF = LIM<>::max(); class SingingEasy { public: int solve( vector <int> pitch ) { const int N = SZ( pitch ); VVI dp( N + 1, VI( N + 1, INF ) ); dp[0][0] = 0; REP( i, N + 1 ) { REP( j, N + 1 ) { const int p = max( i, j ); if ( N <= p || dp[i][j] == INF ) { continue; } dp[ p + 1 ][j] = min( dp[ p + 1 ][j], dp[i][j] + ( i ? abs( pitch[p] - pitch[ i - 1 ] ) : 0 ) ); dp[i][ p + 1 ] = min( dp[i][ p + 1 ], dp[i][j] + ( j ? abs( pitch[p] - pitch[ j - 1 ] ) : 0 ) ); } } int res = INF; REP( i, N + 1 ) { res = min( res, dp[i][N] ); res = min( res, dp[N][i] ); } return res; } };
