Range Flip の解説

dp[i][j][k] := i番目までのカードをどちらでおくか決めた時、ひっくり返した回数がj回、直前をひっくり返したか = k(0, 1)

としてdpすれば良いです。 k = 1の時はrangeでflipしたとして無料で今のカードをひっくり返せます。 そうでない時はjのコストを1払ってひっくり返す必要があります。

fn main() {
    input! {
        n: usize, kk: usize,
        ab: [(isize, isize); n]
    }
    let mut dp = vec![vec![vec![-1; 2]; kk + 1]; n + 1];
    dp[0][0][0] = 0;
    for (i, j, k) in iproduct!(0..n, 0..=kk, 0..2) {
        if dp[i][j][k] == -1 {
            continue;
        }
        let now = dp[i][j][k];
        let (a, b) = ab[i];
        dp[i + 1][j][0].chmax(now + a);
        if k == 1 {
            dp[i + 1][j][1].chmax(now + b);
        }
        if k == 0 && j + 1 <= kk {
            dp[i + 1][j + 1][1].chmax(now + b);
        }
    }
    let ans = dp[n].iter().flatten().max().unwrap();
    println!("{}", ans);
}