D - Strange Lunchbox

[hxrxchang]

https://atcoder.jp/contests/abc219/tasks/abc219_d

問題概要

N個の弁当箱にそれぞれたこ焼きとたい焼きが A[i], B[i] 個入っている。 たこ焼きX個以上、たい焼きY個以上にするための最小の弁当の個数を求めよ。

制約

• 1 <= N <= 300
• 1 <= X, Y <= 300
• 1 <= A, B <= 300

解き方

またもやめっちゃDP感が強い。

• 弁当が1個目まで、2個目まで、3個目まで... それぞれの際に　"たこ焼きとたい焼きの個数をある数字にするのに最小の弁当の数"、は独立して考えられる
  • 部分構造最適性 がある
• 上記の問題は同一の部分問題を繰り返して解くことができる
  • 部分問題重複性 がある

たこ焼きがx個 ∧ たい焼きがy個 (x, yは任意の数字) になるのには、 [][]int の2次元配列で管理すればいい。(x, yを独立に考えてはだめ)。

const maxCnt = 300

func solve() {
    n := getInt()
    in := getInts()
    x, y := in[0], in[1]
    boxes := make([][]int, n)
    for i := 0; i < n; i++ {
        boxes[i] = getInts()
    }

    // dp[i][j]: たこ焼きをi個、たい焼きをj個作るのに必要な最小の箱の数
    dp := make([][]int, maxCnt+1)
    for i := 0; i <= maxCnt; i++ {
        dp[i] = make([]int, maxCnt+1)
        for j := 0; j <= maxCnt; j++ {
            dp[i][j] = BIGGEST
        }
    }
    dp[0][0] = 0

    for _, box := range boxes {
        tmp := copy2DSlice(dp)
        a, b := box[0], box[1]
        for i := 0; i <= maxCnt; i++ {
            for j := 0; j <= maxCnt; j++ {
                // x, y以上は同じ扱いにする
                tmp[min(i+a, x)][min(j+b, y)] = min(tmp[min(i+a, x)][min(j+b, y)], dp[i][j]+1)
                tmp[i][j] = min(tmp[i][j], dp[i][j])
            }
        }
        dp = tmp
    }

    if dp[x][y] == BIGGEST {
        fmt.Println(-1)
    } else {
        fmt.Println(dp[x][y])
    }
}

https://atcoder.jp/contests/abc219/submissions/54679428