AOJ 0597 Xiao Long Bao

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0597

解法

汁が飛び散る範囲が小さいので，それを利用します．
ある連続する8個の区間を考えると，そのなかで各小籠包がどの順で食べられるかさえわかれば，答えを求めることができます．
7! = 5040 なので，以下の dp を考えます．
dp[i][p] := 右端を i 番目まで見た時に，そこから ( i 番目も含めて) 手前7個の食べる順番が p であるようなときの最大
ただし，p は順列です．

dp[i][p] の状態から遷移を考えます．区間内の小籠包が互いにどれだけ点数を与えるかはすでに求まっているということになるので，新しい i + 1 番目の小籠包を p に付け加えることになります．
付け加える前に，i - 6 番目（つまり左端）の小籠包は今後みるひつようがないので，取り除きます．この小籠包が x 番目に食べられるとするなら，区間内の y ( < x) 番目に食べられる小籠包を，y + 1 番目に食べられるということにしておきます．
つぎに，i + 1 番目の小籠包が，区間内で何番目に食べられるかをすべて試します．k 番目に食べられるとするなら，そこから距離 d[i + 1] 以内で，かつ自分よりあとに食べることになる小籠包の数だけ，a[i + 1] を加算します．また，k 番目より先に食べる小籠包についても，同様に考えて加算します．
さて，先程取り除いた左端の小籠包ですが，もし i + 1 番目の小籠包，あるいは左端の小籠包の汁の飛び散る範囲が 7 なら，この2つの順番も考慮する必要があります．
これは，i + 1 番目の小籠包も x 番目に食べるとしたときに，左端の小籠包とどちらを先に食べるか（これは自由に決めて良い．なぜなら他の小籠包の順番はもう決まっていて，これとは独立だから．）を試して良い方を取ります．
それ以外のときは，他の小籠包と同様に単純に x と k を比較すれば良いです．

以上で解くことが出来ました．
計算量は O(n * 7 * 6 * 7!) となり，間に合います．

ソースコード

fn next_permutation<T: Ord>(v: &mut Vec<T>) -> bool {
    if v.len() == 0 || v.len() == 1 {
        return false
    }
    let mut i: usize = v.len() - 1;
    let n = v.len();
    loop {
        let ii = i;
        i -= 1;
        if v[i].cmp(&v[ii]) == Ordering::Less {
            let mut j = n - 1;
            while v[i].cmp(&v[j]) != Ordering::Less {
                j -= 1;
            }
            v.swap(i, j);
            for k in 0..(n - ii) / 2 { // reverse
                v.swap(ii + k, n - k - 1);
            }
            return true
        }
        if i == 0 { // i == first
            v.reverse();
            return false
        }
    }
}
 
fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);
 
    let n: usize = sc.read();
    let mut d: Vec<usize> = vec![0; n];
    let mut a: Vec<usize> = vec![0; n];
    for i in 0..n {
        d[i] = sc.read();
    }
    for i in 0..n {
        a[i] = sc.read();
    }
    let d = d;
    let a = a;
 
    let mut dp: Vec<HashMap<Vec<usize>, usize>> = vec![HashMap::new(); n];
    let mut perm: Vec<usize> = (0..7).collect();
    while {
        dp[0].insert(perm.clone(), 0);
        next_permutation(&mut perm)
    } {}
 
    for i in 0..n-1 {
        let mut nxt: HashMap<Vec<usize>, usize> = HashMap::new();
        for (p, r) in &mut dp[i] {
            let mut np: Vec<usize> = vec![0; 7];
            for j in 0..6 {
                np[j] = p[j + 1];
                if p[0] > p[j + 1] {
                    np[j] += 1;
                }
            }
            for _j in 0..7 {
                let mut rr = *r;
                for kk in 0..6 {
                    if i >= kk {
                        if np[6 - kk - 1] < np[6] && d[i - kk] >= kk + 1 {
                            rr += a[i - kk];
                        }
                        if np[6 - kk - 1] > np[6] && d[i + 1] >= kk + 1 {
                            rr += a[i + 1];
                        }
                    }
                }
                if i >= 6 && p[0] == np[6] {
                    let t1 = if d[i - 6] == 7 { a[i - 6] } else { 0 };
                    let t2 = if d[i + 1] == 7 { a[i + 1] } else { 0 };
                    rr += max(t1, t2);
                } else if i >= 6 && p[0] > np[6] {
                    rr += if d[i + 1] == 7 { a[i + 1] } else { 0 };
                } else if i >= 6 && p[0] < np[6] {
                    rr += if d[i - 6] == 7 { a[i - 6] } else { 0 };
                }
                if nxt.contains_key(&np) {
                    let r2: usize = *nxt.get(&np).unwrap();
                    nxt.insert(np.clone(), max(rr, r2));
                } else {
                    nxt.insert(np.clone(), rr);
                }
                np[6] += 1;
                for k in 0..6 {
                    if np[k] == np[6] {
                        np[k] -= 1;
                    }
                }
            }
        }
        dp[i + 1] = nxt;
    }
 
    println!("{}", dp[n - 1].iter().fold(0, |ans, (_, a)| max(ans, *a)));
}

感想

これは普通に難しかった．遷移が少しややこしい．