AtCoder ABC #145 E All-you-can-eat

問題

E - All-you-can-eat

解説

他の回答を見つつ、公式解説の解法２に沿って回答を作成。

DP難しい。。。

fn solve(t: usize, abs: Vec<(usize, usize)>) -> usize {
    use std::cmp::max;

    let mut abs = abs;
    abs.sort_by_key(|x| x.0);

    let mut dp = vec![0; t + 3001];

    for &(a, b) in abs.iter() {
        for i in (0..t).rev() {
            dp[i + a] = max(dp[i] + b, dp[i + a]);
        }
    }

    dp.into_iter().max().unwrap()
}