The Diversity of Prime Factorization [RUPC2018 Day3 D]

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753033

DPで解く。
前から順番にpとするかeとするかを決めていくのだが、それぞれ条件がある

• A[i]をpにするには
  • (前回のp)＜A[i]
  • A[i]が素数
• A[i]をeにするには
  • 直前の要素がeでない

条件の中で(前回のp)が出てくるので、これが問題になる。
考察すると「pは2要素以上離れることはない」ということが分かる。
p e eのような列は認められないためである。
よって、前回のpは1つ前か2つ前のどちらかだけであり、その情報だけを記録しておけばいいことが分かる。
よって、以下のDPで解こう。
「dp[i][j] := i番目まででj個前が前回のp」
遷移や条件はそのままコードになっているので、そちらを読むほうが分かりやすいだろう。
するとdp[N][1]+dp[N][2]が答え。

int N, A[101010];
mint dp[101010][3];
// dp[i][j] := i番目まででj個前がpとして使われている
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    if (!isprime(A[0])) {
        printf("0\n");
        return;
    }

    dp[1][1] = 1;
    rep(i, 1, N) rep(j, 1, 3) {
        // 新しくpを作る
        if (isprime(A[i]) and 0<=i-j and A[i - j] < A[i]) dp[i + 1][1] += dp[i][j];

        // 累乗にする
        if (j == 1) dp[i + 1][2] += dp[i][j];
    }

    mint ans = dp[N][1] + dp[N][2];
    cout << ans << endl;
}