백준 13555 / C++

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

13555번: 증가하는 부분 수열

 

[풀이]

naive하게 세워보자. dp[i][j]를 A1~Ai까지 길이 j인 증가 부분수열의 개수라고 하자. 

dp[i][j]=sum(dp[k][j-1])이 된다. (단, a[k]<a[i] ) 이걸 단순히 돌리면 매번 k를 찾아주는데 O(N)이 들기 때문에

O(KN^2) 으로 TLE가 난다. 이런 k의 합을 O(logN)에 해결하고 싶다. 세그트리로 풀어주자. 

값을 인덱스로 하는 세그트리에서 [1, a[i]-1]에서의 합으로 잘 처리해주면 될 것 같다.

길이별로 세그트리를 만들어서  tree[j-1]의 구간 [1,a[i]-1]에서 값이 sum(dp[k][j-1])가 된다.

이제 dp[i][j]를 구했으니 tree[j]의 a[i] 인덱스에 dp[i][j]를 업데이트해주면 된다. 

기본 재귀세그로 짜면 TLE가 나니까 구현도 쉽고 시간도 우월한 펜윅으로 해주자. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 100010;
const ll mod = 5000000;
ll n, k, a[MAX], tree[55][MAX], dp[MAX][55];

// update tree[len][idx] 
void upd(int len, int i, ll v) {
	while (i <= MAX) {
		tree[len][i] += v;
		tree[len][i] %= mod;
		i += i & -i;
	}
}

// sum x in tree[len]
ll sum(int len, int i) {
	ll ret = 0;
	if (len == 0) return 1;
	while (i) {
		ret += tree[len][i];
		ret %= mod;
		i -= i & -i;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			// dp[i][j]=sum(dp[t][j-1]) (a[t]<a[i])
			dp[i][j] = sum(j - 1, a[i] - 1);
			// tree[j]의 a[i]인덱스에 dp[i][j] 갱신 
			upd(j, a[i], dp[i][j]);
		}
	}
	// dp[1][k]+...+dp[n][k]
	cout << sum(k, MAX) << '\n';
}