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

핵심 아이디어

<aside> 💡

LIS dp

$dp_{ij}$를 $i$가 마지막 원소인 길이가 $j$인 부분수열의 개수 라고 정의하면

$dp_{ij} = \sum_{k=-10,000}^{i-1}dp_{kj-1}$

가 성립한다.

</aside>

인덱스에 $-10,000$이 들어갈 수 있도록 입력되는 모든 $a$에 $\text{base}$를 더한다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

const int base = 10'001;

int n, k;
int a[101];
ll dp[20'020][101];

void solve()
{
    memset(dp, 0, sizeof(dp));

    for(int i = 0; i<n; i++){
        cin >> a[i];
        a[i] += base;
    }
    
    dp[0][0] = 1;
    for(int i = 0; i<n; i++){
        for(int cnt = 0; cnt<k; cnt++){
            for(int val = 0; val<a[i]; val++){
                if(dp[val][cnt]){
                    dp[a[i]][cnt+1] += dp[val][cnt];
                }
            }
        }    
    }
    
    ll ans = 0;
    for(int val = 0; val<=20'001; val++){
        ans += dp[val][k];
    }
    cout << ans <<"\\n";
}

signed main()
{
    FASTIO;
    while(true){
        cin >> n >> k;
        if(n == 0 && k == 0) break;
        solve();
    }

    return 0;
}