aoj 0550 - Dividing Snacks

問題

問題概要

お菓子に１ミリずつ切り目があり、切れ目ごとに切るためのコストが異なる。コストを最小にして、お菓子を半分ずつに分ける方法は。

解法

dpでとく。
dp[i][j][k] :=　(お菓子の長さがiでAさんの文がjの時で次ににkさんがお菓子をもらう時の切断する時の秒数が最小の時間) (k==0:A k==1:B)のようにしてやる。これはお菓子の長さを伸ばす ような形で考えている。また、お菓子を切断した後、切断する前の部分と切断した後の部分を同じ人に渡すなら、切る必要がなかったということになるので、切った場合は次はもう一方の人にお菓子を渡す と考えていい。このように考えると、漸化式は
お菓子を切らない時
dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k]) (k = 0)
dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]) (k = 1)
お菓子を切る時
dp[i + 1][j + 1][1] = min(dp[i + 1][j + 1][1], dp[i][j][k] + v[i]) (k = 0)
dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][k] + v[i]) (k = 1)
となる。切らない場合は、次回お菓子をもらう人は変化せず、もらう場合は、お菓子をもらう人が変化している。
ただし、このままだと、ミスの所にあるような回答になり、MLEとなってしまう。そこで、漸化式がiに対して2項間漸化式であることを利用して(dp[i + 1]を求める時、dp[i]のみを使う)、一つ 前のdpの値のみを保持しておけば良いので、iをmod2をとりながら、同じメモリ空間を使いまわせば、MLEを回避できる。

ミス

MLE回答 多分制限がなければ、AC

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

//dp[i][j][k] :=　(お菓子の長さがiでAさんの文がjの時で次ににkさんがお菓子をもらう
//時の切断する時の秒数が最小の時間) (k==0:A k==1:B)
int dp[10010][5010][2];
int main(void){
    int n; cin >> n;
    vector<int> v(n);
    rep(i, n - 1) cin >> v[i];
    rep(i, 10010)rep(j, 5010)rep(k, 2)dp[i][j][k] = INF;

    dp[0][0][0] = 0;
    dp[0][0][1] = 0;
    //配るdp
    for (int i = 0; i < n; ++i){
        for (int j = 0; j <= n / 2; ++j){
            for (int k = 0; k < 2; ++k){
                if(dp[i][j][k] == INF) continue;
                //お菓子を切らない時
                if(k == 0){
                    dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k]);
                }else{
                    dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
                }
                //お菓子を切る時
                if(k == 0){
                    dp[i + 1][j + 1][1] = min(dp[i + 1][j + 1][1], dp[i][j][k] + v[i]);
                }else{
                    dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][k] + v[i]);
                }
            }
        }
    }

    int ans = INF;
    rep(k, 2){
        ans = min(ans, dp[n][n / 2][k]);
    }
    cout << ans << endl;
}

コード

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

//dp[i][j][k] :=　(お菓子の長さがi(mod2)でAさんの文がjの時で次ににkさんがお菓子をもらう
//時の切断する時の秒数が最小の時間) (k==0:A k==1:B)
int dp[2][5010][2];
int main(void){
    int n; cin >> n;
    vector<int> v(n);
    rep(i, n - 1) cin >> v[i];
    rep(i, 2)rep(j, 5010)rep(k, 2)dp[i][j][k] = INF;

    dp[0][0][0] = 0;
    dp[0][0][1] = 0;
    //配るdp
    for (int i = 0; i < n; ++i){
        rep(j, 5010)rep(k, 2)dp[(i + 1) % 2][j][k] = INF;//dpを再利用するため
        for (int j = 0; j <= n / 2; ++j){
            for (int k = 0; k < 2; ++k){
                if(dp[i % 2][j][k] == INF) continue;
                //お菓子を切らない時
                if(k == 0){
                    dp[(i + 1) % 2][j + 1][k] = min(dp[(i + 1) % 2][j + 1][k], dp[i % 2][j][k]);
                }else{
                    dp[(i + 1) % 2][j][k] = min(dp[(i + 1) % 2][j][k], dp[i % 2][j][k]);
                }
                //お菓子を切る時
                if(k == 0){
                    dp[(i + 1) % 2][j + 1][1] = min(dp[(i + 1) % 2][j + 1][1], dp[i % 2][j][k] + v[i]);
                }else{
                    dp[(i + 1) % 2][j][0] = min(dp[(i + 1) % 2][j][0], dp[i % 2][j][k] + v[i]);
                }
            }
        }
    }

    int ans = INF;
    rep(k, 2){
        ans = min(ans, dp[n % 2][n / 2][k]);
    }
    cout << ans << endl;
}