AOJ 2849 Route Calculator

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2849

問題概要

グリッドに数字または'+', '*'が与えられる。
$ (1,1) $から $ (h,w) $まで右または下への移動をするとき、通ったマスの文字を順番に並べてできる式の値の最大値を答える。
ただし$ i+j $が奇数の箇所は'+'か'*'、偶数の箇所は数字であること、また$ h+w $は偶数であることが保証されている。
式の値が$ 1e15 $より大きくなる場合は$ -1 $を出力する。

解法

$ dp[i][j][val] = (i,j)までみて現在の積の値がvalの時の最大値 $
をmapでもって回すとTLE(MLE)するので別方針を考える必要がある。

*でつながっているところを一気にみて、それらを+で連結することを考え、以下のものを求めていく。

$mul[i][j][k][l] = (i,j)から(k,l)までの積の最大値$
$dp[i][j] = (i,j)から出発するときの現在の和の最大値$

遷移できる候補は$ (i,j)→(i+2,j), (i+1, j+1), (i,j+2) $の3通り。
記号を見て遷移して良いかを見ることで適切に遷移できる。(例えば$dp[i][j]→dp[i][j+2]はs[i][j+1]=='+'のときのみ$)

• $ mul $の前計算を先にしてから+の遷移をするイメージ
• $ dp[i][j] $を$ (i,j) $から出発するときの最大値と定義してしまったので、$ dp[h+1][w+1] $を答える。$ s $の右段と下段に'+'を追加する。
  
• $ 1e15 $まではokなのでINFの値を$ 1e15+1 $にする(ここ重要)

実装

mulを貰うDPで、dpを配るDPで書いたので分かりずらいかも。

template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
    if(a<b){
        a = b; return true;
    }
    else return false;
}

ll mul[55][55][55][55];
ll dp[55][55];

int main(){
    int h,w; cin >> h >> w;
    vector<string> s(h); rep(i,h) cin >> s[i];
    ll INF = (ll)1e15+1;
    rep(i,h) s[i].push_back('+');
    s.push_back(string(w+1,'+'));
    rep(i,h) rep(j,w) rep(k,h) rep(l,w){
        dp[i][j] = mul[i][j][k][l] = 0;
    }
    dp[0][0] = 0;
    rep(i,h) rep(j,w) if((i+j)&1^1) mul[i][j][i][j] = s[i][j] - '0';
    rep(k,h) rep(l,w){
        if((k+l)&1) continue;
        rep(i,h) rep(j,w){
            if(i>k || j>l) continue;
            ll c = s[k][l] - '0';
            if(k>=2 && s[k-1][l] == '*') chmax(mul[i][j][k][l], min(INF, mul[i][j][k-2][l] * c));
            if(l>=2 && s[k][l-1] == '*') chmax(mul[i][j][k][l], min(INF, mul[i][j][k][l-2] * c));
            if(k>=1 && l>=1 && (s[k-1][l] == '*' || s[k][l-1] == '*')){
                chmax(mul[i][j][k][l], min(INF, mul[i][j][k-1][l-1] * c));
            }
        }
    }
    rep(k,h) rep(l,w){
        if((k+l)&1) continue;
        rep(i,h) rep(j,w){
            if(i>k || j>l) continue;
            ll res = min(INF, dp[i][j] + mul[i][j][k][l]);
            if(s[k+1][l] == '+') chmax(dp[k+2][l], res);
            if(s[k][l+1] == '+') chmax(dp[k][l+2], res);
            if(s[k+1][l] == '+' || s[k][l+1] == '+') chmax(dp[k+1][l+1], res);
        }
    }
    if(dp[h][w] == INF) dp[h][w] = -1;
    cout << dp[h][w] << endl;
}