概要
重み付き区間が m 個与えられる。
この区間群から、一つ以上の区間によって被覆されている部分の長さが k 以上になるようにいくつかの区間を選ぶ。
このときの重みの総和の最小値を求めよ。
解法
dp[ 何番目まで考慮したか ][ 何箇所被覆したか ] := このときの重みの最小値
として動的計画法をすると答えが求まります。
初期状態は dp[ 0 ][ 0 ] = 0 で、状態遷移は次のようになります
- dp[ i ][ j ] -> dp[ i + 1 ][ j ]
- dp[ i ][ j ] から i 以降の各点に対し、最も軽い区間で被覆する遷移
コード
typedef long long LL; typedef vector<int> VI; typedef vector<VI> VVI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) const int INF = INT_MAX; const LL LINF = LLONG_MAX / 4; int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n, m, k; cin >> n >> m >> k; VVI G( n, VI( n, INF ) ); REP( i, 0, m ) { int l, r, c; cin >> l >> r >> c; l--; r--; REP( j, l, r + 1 ) { G[j][r] = min( G[j][r], c ); } } vector< vector<LL> > dp( n + 1, vector<LL>( n + 1, LINF ) ); dp[0][0] = 0; REP( i, 0, n ) { REP( j, 0, n ) { dp[ i + 1 ][j] = min( dp[ i + 1 ][j], dp[i][j] ); REP( k, i, n ) { if ( G[i][k] == INF ) { continue; } dp[ k + 1 ][ j + k - i + 1 ] = min( dp[ k + 1 ][ j + k - i + 1 ], dp[i][j] + G[i][k] ); } } } LL res = LINF; REP( i, k, n + 1 ) { res = min( res, dp.back()[i] ); } cout << ( res == LINF ? -1 : res ) << endl; return 0; }