2854번: 문제 출제

https://www.acmicpc.net/problem/2854


$O(n)$


난이도가 하나인 문제 수 배열을 ai, 난이도가 두개인 문제 수 배열을 bi라하자.(bi는 i, i+1번으로 출제 될 수 있다.)
dp[i][0]: i번까지 출제 했을 때, ai에서 출제하는 경우의 수
dp[i][1]: i번까지 출제 했을 때, bi에서 출제하는 경우의 수
라고 정의하자.
점화식을 세우면
dp[i][0]=dp[i-1][0]*(a[i]+b[i-1]) + dp[i-1][1]*(a[i]+b[i-1]-1)
dp[i][1]=(dp[i-1][0]+dp[i-1][1])*b[i]

구하고자 하는 답은 dp[n][0]이 된다.

#include<stdio.h>
#define sosu ((int)1e9+7)
const int MAX_N = 1e5;
int dp[MAX_N + 1][2], a[MAX_N + 1], b[MAX_N + 1], n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i < n; i++) scanf("%d", b + i);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        dp[i][0] = ((long long)(dp[i - 1][0] + dp[i - 1][1])*(a[i] + b[i - 1] - 1) + dp[i - 1][0]) % sosu,
        dp[i][1] = (long long)(dp[i - 1][0] + dp[i - 1][1])*b[i] % sosu;
    printf("%d", dp[n][0]);
    return 0;
}