yukicoder No.10 ＋か×か

No.10 ＋か×か - yukicoder

問題概要

列に並んだ数列 を順番を変えずに加法・乗法で結び、 に等しくなるように式を作る。ただし演算は左から順に行うものとし、辞書順最小の演算子列を求める。

解法

文字列を持ってDP。計算量がちょっとだけ大きいがまあ間に合う。 文字コードが '*' '+' '.' であることを利用した。

int main() {
    ll N, M;
    cin >> N >> M;
    ll A[N];
    rep(i, N) cin >> A[i];
    string DP[N][M + 1];
    DP[0][A[0]] = ".";
    rep(i, N - 1) {
        rep(j, M) {
            if (j + A[i + 1] <= M) {
                chmax(DP[i + 1][j + A[i + 1]], DP[i][j] + '+');
            }
            if (j * A[i + 1] <= M) {
                chmax(DP[i + 1][j * A[i + 1]], DP[i][j] + '*');
            }
        }
    }
    cout << DP[N - 1][M].substr(1, DP[N - 1][M].size() - 1) << endl;
}