WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #186 Div2 D "Ilya and Roads"

問題

http://codeforces.com/contest/313/problem/D

イリヤの住む町を、誰もが素晴らしい町だと言う。・・・道路の状態を除けば。実は、ZooVilleのただ1つの道は1列に並んだn個の穴といってもいい。この穴を左から右へと、1からnの番号を振ってあるとする。

イリヤは自分の町に支援を続けたいと心から思っている。それで、彼はただ1つのZoovilleの道路の穴を、少なくともk個埋めたいと思っている。

この町には会社がm社ある。i番目の会社はl_iからr_iの穴を埋めることができ、それにc_i円必要とする。ZooVilleの会社は貪欲なので、受け持つ範囲に穴が既にいくつか埋められていたとしても、金額を値引きする事は無い。

少なくともk個の穴を埋めるためにイリヤが必要とする最小の金額を出力せよ。

制約

1 <= n <= 300
1 <= m <= 10^5
1 <= c_i <= 10^9



考えた事

dp[ 考えている穴 ][ そこまでに埋めた穴の数 ] = 最小の金額・・でDP

初期化

dp[ i ][ j ] = INF ( 0 <= i, j <= n )
dp[ 0 ][ 0 ] = 0

更新

・会社を利用しない場合
dp[ hole+1 ][ fix ] を dp[ hole ][ fix ] とで最小をとる

・考えている穴から範囲を持っている(つまりl_i)会社を利用する場合
全範囲使えば
dp[ r_i+1 ][ fix + ( r_i - l_i + 1 ) ]を dp[ hole ][ fix ] + c_i とで最小をとる
でいいが、
f:id:Ekaing:20130606235901p:plain
みたいに範囲が重なったときに対応できないので
dp[ hole+1 ][ fix+1 ]
dp[ hole+2 ][ fix+2 ]
dp[ hole+3 ][ fix+3 ]
...
もそれぞれ最小をとっていく

結果

最終的にdp[ hole ][ fix ]において、fixがk以上であるやつ全部の最小が答え



ソースコード

typedef long long I64;

I64 dp[310][310];
int L[100010], R[100010], C[100010];


int main() {

    int n, m, k;
    cin >> n >> m >> k;

    // 穴と会社を結びつける
    vector<int> Cs[310]; //Cs[i] : i番目の穴から埋めれる会社のリスト
    for( int i = 0; i < m; i++ ){
        cin >> L[i] >> R[i] >> C[i];
        Cs[L[i]].push_back( i );
    }

    // 初期化
    const I64 INF = 1e10 * 300;
    for( int i = 0; i <= n + 1; i++ ){
        for( int j = 0; j <= n; j++ ){
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    
    // 更新
    for( int hole = 0; hole <= n; hole++ ){
        for( int fix = 0; fix <= n; fix++ ){
            if( dp[hole][fix] == INF ) continue;

            // 会社に依頼しない
            dp[hole+1][fix] = min( dp[hole+1][fix], dp[hole][fix] );

            // 会社に依頼する
            for( int c = 0; c < Cs[hole].size(); c++ ){
                int id = Cs[hole][c];
                for( int r = L[id] + 1; r <= R[id] + 1; r++ ){
                    int len = r - L[id];
                    dp[r][fix+len] = min( dp[r][fix+len], dp[hole][fix] + C[id] );
                }
            }
        }
    }

    // 集計
    I64 ans = INF;
    for( int i = 1; i <= n + 1; i++ ){
        for( int j = k; j <= n; j++ ){
            ans = min( ans, dp[i][j] );
        }
    }

    if( ans == INF ) ans = -1;
    cout << ans << endl;
}