0w1

CFR 313 D. Ilya and Roads ( DP )

Problem - D - Codeforces
We can first precompute mincost array where
mincost[ i ][ j ]: minimum cost required to, fix all holes that hadn't yet been, starting from i until j
dp[ i ][ j ]: minimum cost required when, finished examining i holes, and fixed j holes among them
now we have
dp[ i ][ 0 ] = 0 Ɐ 0 ≤ i ≤ n
dp[ i ][ j ] = min{ dp[ i - 1 ][ j ], dp[ i - k ][ j - k ] + mincost[ i - k + 1 ][ i ] Ɐ j - k ≥ 0 } Ɐ j ≤ i ≤ n
we will not drop optimal solutions as it recurs, because when we are on some hole i that we have finished examining all holes before it and including it, now if there is a choice to start a segment [ i + 1, ? ] with some cost, if the optimal solution is to choose it and stop somewhere for some reason, it will, for how we precomputed the mincost array. It should never go across that hole i + 1, coming back and regret that it was not chosen since it is never better to leave hole i + 1 empty in that case. Also, the answer will be dp[ n ][ k ], and does not have to be min{ dp[ n ][ x ] } Ɐ k ≤ x , because the optimal solution having already k holes fixed will be able to make the decision to refuse adding anymore new segments exactly since it had.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e16;
const int MAXN = 300 + 2;
const int MAXM = 1e5 + 5;
const int MAXC = 1e9 + 2;

template<class T1, class T2> bool upmin(T1 &a, T2 b){
    if( a <= b ) return false;
    a = b; return true;
}

int n, m, k;
int l[ MAXM ], r[ MAXM ], c[ MAXM ];

ll dp[ MAXN ][ MAXN ]; // now finished hole i, fixed j
ll mincost[ MAXN ][ MAXN ]; // minimum cost to fix until j, when now on i

void solve(){
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            dp[ i ][ j ] = mincost[ i ][ j ] = INF;
    for(int i = 0; i < m; ++i)
        for(int j = l[ i ]; j <= r[ i ]; ++j)
            upmin( mincost[ l[ i ] ][ j ], c[ i ] );            

    for(int i = 0; i <= n; ++i)
        dp[ i ][ 0 ] = 0LL;
    for(int i = 0; i < n; ++i) // there are i previous holes walked through
        for(int j = 0; j <= i; ++j){ // finished examining i holes, and fixed j of them
            upmin( dp[ i + 1 ][ j ], dp[ i ][ j ] );
            for(int k = 1; i + k <= n; ++k) // fix k holes and move to hole i + k
                upmin( dp[ i + k ][ j + k ], dp[ i ][ j ] + mincost[ i + 1 ][ i + k ] );
        }
    
    if( dp[ n ][ k ] < INF ) cout << dp[ n ][ k ] << endl;
    else cout << -1 << endl;
}

int main(){
    ios::sync_with_stdio( false );
    cin >> n >> m >> k;
    for(int i = 0; i < m; ++i)
        cin >> l[ i ] >> r[ i ] >> c[ i ];
    solve();
    return 0;
}