Quartz 5

部分和

Properties1
tags競プロ

2 min read

  • DP

  • ABC204 D - Cooking - かんプリンの学習記録

  • オーブン1個

    • sum_{i in 0..N} T_i

  • オーブン2個†

    • T = A B, max(sum_{i in A} T_i, sum_{i in B} T_i)
      • S = sum_{i in 0..N} T_i とすると
      • max(S_A := sum_{i in A} T_i, S - S_A)
      • なので, これを最小にする A の割当を決める
      • 前者のほうが小さいとすると
        • ans = 後者
        • S_A S/2
      • min S - S_A -> max S_A
use proconio::input;
 
fn main() {
    input! {
        n: usize,
        ts: [usize; n],
    };
    let s = ts.iter().sum::<usize>();
    let mut dp = vec![vec![false; s + 1]; n + 1];
    // dp[i][j] == true: sum of exist A in ts[0..i] == j
    for i in 0..n {
        dp[i][0] = true;
    }
    for i in 0..n {
        for j in 0..=s {
            if j >= ts[i] {
                dp[i + 1][j] = dp[i + 1][j] || dp[i][j - ts[i]] || dp[i][j];
            }
        }
    }
    let s_a = dp[n][0..=(s / 2)]
        .iter()
        .enumerate()
        .rev()
        .find_map(|(i, e)| e.then_some(i))
        .unwrap_or(0);
    println!("{}", s - s_a);
}

Graph View

Backlinks