백준 34984번: gmb 수열 [C++]

작성일 | In
플래티넘 III 플래티넘 III

문제

gmb 수열

풀이

$dp[i][j]$를 $\cdots, i, j$처럼 끝나는 부분수열의 개수, $p[i][j]$를 등장한 값들의 순서쌍 $(i, j)$의 개수라 합시다.

첫 번째 원소부터 마지막 원소까지 훑으면서 $p[i][j]$를 갱신하고, $dp[i][j]$에 $dp[i + j][i] + p[i + j][i]$를 더하는 방식으로 갱신하면 문제를 해결할 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

constexpr int MAX_N = 202020, MAX_B = 333, MOD = 1e9 + 7;

int B[MAX_N], dp[MAX_B][MAX_B], cnt[MAX_B], pairCnt[MAX_B][MAX_B];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
        cin >> B[i];

    for (int i = 1; i <= N; i++) {
        int z = B[i];
        for (int y = 0; y < MAX_B; y++) {
            int x = y + B[i];

            if (x >= MAX_B)
                continue;

            dp[y][z] += (dp[x][y] + pairCnt[x][y]) % MOD;
            dp[y][z] %= MOD;
        }

        for (int B_j = 0; B_j < MAX_B; B_j++) {
            pairCnt[B_j][z] += cnt[B_j];
            pairCnt[B_j][z] %= MOD;
        }
        cnt[B[i]]++;
    }

    int answer = 0;
    for (int x = 0; x < MAX_B; x++) {
        for (int y = 0; y < MAX_B; y++) {
            answer += dp[x][y];
            answer %= MOD;
        }
    }

    cout << answer;

    return 0;
}

백준 34984번: gmb 수열 [C++]