AtCoder Beginner Contest 145 F - Laminate

問題

 H_{i}のいずれとも異なる高さに変更する意味はないので、 a_{i}:=i番目に小さい列の高さとおき、 a_{i}に高さを変更する場合を考える。 左端から塗っていくことを考えると、新たに塗り直さなければならない回数は最も右側の列の高さから求められるので、以下のようなdpを考えられる。

 dp_{i,j,k} := i列目まで見たとき、このうちj個の高さを変更したとき、i列目の高さがa_{k}であるときの最小コスト

遷移式は、 a_{k} = h_{i-1} のとき、

 dp_{i,j,k} =  min(x, min_{l=0}^{H}\{ dp_{i-1,j,l}+max(0, k-l)\})

となり、そうでないとき、

 dp_{i,j,k}=x

となる。ただし、 x= min_{l=0}^H \{dp_{i-1,j-1,l} + max(0, k-l) \}である。

これをそのまま計算すると O(N^{4})となってしまうので工夫する必要がある。

まず、a_{k}=h_{i-1}となるのは各(i,j)に対して一度だけなので、min_{l=0}^{H}\{ dp_{i-1,j,l}+max(0, k-l)\}はそのままでもよく、各(i,j,k)に対してxO(1)で求めることを考えれば良い。

 max(0, k-l)の項に注目すると、


x=min(a_{k}+min_{l=0}^{k}\{dp_{i-1,j-1,l}-a_{l}\}, min_{l=k}^{H}\{dp_{i-1,j-1,l}\})

と変形することができる。ここで、

 b_{i,j,k} = min_{l=0}^{k}\{dp_{i-1,j-1,l}-a_{l}\}

 c_{i,j,k} = min_{l=k}^{H}\{dp_{i-1,j-1,l}\}

と定義すると、各 k=0,...,Hについて b_{i-1,j-1,k} c_{i-1,j-1,k}を予め求めておくことで、 dp_{i,j,k}O(1)で更新できる。

...

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    rep(i, n)
    {
        cin >> h[i];
    }

    vector<int> a(n);
    copy(h.begin(), h.end(), a.begin());
    a.push_back(0);
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    const int64_t M = 1'000'000'000L * n;
    vector<vector<vector<int64_t>>> dp(n + 1, vector<vector<int64_t>>(k + 1, vector<int64_t>(a.size())));
    irep(i, n) irep(j, k)
    {
        if (i == 0) {
            rep(l, a.size())
            {
                dp[i][j][l] = j == 0 && l == 0 ? 0 : M;
            }
        } else {
            rep(l, a.size())
            {
                dp[i][j][l] = M;
                if (a[l] == h[i - 1]) {
                    rep(l2, a.size())
                    {
                        dp[i][j][l] = min(dp[i][j][l], dp[i - 1][j][l2] + max(0L, (int64_t)a[l] - a[l2]));
                    }
                }
            }
            if (j > 0) {
                int64_t x = M;
                rep(l, a.size())
                {
                    x = min(x, dp[i - 1][j - 1][l] - a[l]);
                    dp[i][j][l] = min(dp[i][j][l], x + a[l]);
                }

                int64_t y = M;
                rrep(l, a.size())
                {
                    y = min(y, dp[i - 1][j - 1][l]);
                    dp[i][j][l] = min(dp[i][j][l], y);
                }
            }
        }
    }

    int64_t result = M;
    irep(j, k) rep(l, a.size())
    {
        result = min(result, dp[n][j][l]);
    }
    cout << result << endl;

    return 0;
}

遷移式にmax/minが含まれているときは、場合分けすることで式から遷移先の添字を消去することができる場合がある。式に遷移先の添字が含まれていないならば、複数の遷移先で計算結果を共有できる。