AtCoder Beginner Contest 145 F - Laminate

問題ページ
ある列の高さを変更する場合，隣の高さに合わせる以外の中途半端な高さにして解が改善されることはない．よって前からDPを行うとき，番目を変更するならば番目の高さに揃えるとしてよい．番目の高さをのどれに揃えたか？という情報を持っておけばDPの遷移ができる．

番目まで回操作を行った番目の高さが 確定した操作回数 としてDPをする．番目の高さより番目の高さが低い場合，その差の行は操作を行うことが確定する．DPの遷移は

• dp[i][j+1][k] = dp[i-1][j][k] + max(0, a[i]-a[k]) 高さを変更する
• dp[i][j][i] = dp[i-1][j][k] 高さを変更しない

となる．最初の列の高さを変更する場合，0にすることに注意．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
ll dp[305][305][305];  
int main(void) {  
    ll n, m;  
    cin >> n >> m;  
    vector<ll> a(n+1);  
    REP(i, n) cin >> a[i+1];  
  
    REP(i, 305) REP(j, 305) REP(k, 305) dp[i][j][k] = INF;  
    dp[0][0][0] = 0;  
    FOR(i, 1, n+1) REP(j, m+1) REP(k, i) {  
        // 操作しない dp[i+1][j][i] <- dp[i][j][k]  
        ll add = 0;  
        if(a[k] > a[i]) add += a[k] - a[i];  
        chmin(dp[i][j][i], dp[i-1][j][k] + add);  
        // 操作する dp[i+1][j+1][k] <- dp[i][j][k]  
        chmin(dp[i][j+1][k], dp[i-1][j][k]);  
    }  
  
    ll ret = INF;  
    REP(i, m+1) REP(j, n+1) chmin(ret, dp[n][i][j]+a[j]);  
    cout << ret << endl;  
  
    return 0;  
}