blobhyperthink (백준 24505)

안녕하세요. 오늘은 11개짜리 증가를 풀어볼 거예요.

문제

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

아이디어

증가하는 수열의 개수 문제의 쉬운버전입니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll tree[404040] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = 0;
    ll mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll idx, ll val) //idx번지에 val만큼 더하기
{
    if (e < idx || idx < s) return;
    tree[node] += val;
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx, val);
    change(mid + 1, e, node * 2 + 1, idx, val);
}

ll dp[22][101010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, K, i, j, arr[101010] = { 0 };

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

    change(0, N, 1, 0, 1); //dp[0][0]=1
    for (i = 1; i <= 11; i++)
    {
        for (j = 1; j <= N; j++)
        {
            change(0, N, 1, arr[j], dp[i - 1][j]);
            dp[i][j] = SUM(0, N, 1, 0, arr[j] - 1);
            dp[i][j] %= 1000000007;
        }
        init(0, N, 1);
    }

    ll ans = 0;
    for (i = 1; i <= N; i++)
    {
        ans += dp[11][i];
        ans %= 1000000007;
    }
    cout << ans;
}

감사합니다.