Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

PKU 3378 - Crazy Thairs

問題文 : Crazy Thairs

解法 :
dp[i][j] = j番目を終点とする長さi + 1のLISの総数, とすると

すべてのjについてdp[0][j] = 1,

dp[i + 1][j] = Σ[k = 1...j - 1 | a[k] < a[j]]dp[i][k]

となります. Σの部分の計算をBITを使うと, O(nlogn)時間でこの問題を解くことができます.

あと, 50000 C 5 > 2^63 - 1 なので, long long型でも答えが収まりません. 諦めて多倍長を組みましょう. (僕はここのライブラリそのままぺたりしました.)

コード :

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

#define N (50000)

typedef long long lint;

/* ライブラリは省略 */

using namespace std;

int n;

void add(bigint *bit, int k, bigint val)
{
	while (k <= n){
		bit[k] += val;
		k += k & -k;
	}
}

bigint sum(bigint *bit, int k)
{
	bigint ret = 0;
	while (k){
		ret += bit[k];
		k &= (k - 1);
	}
	return (ret);
}

int main(void)
{
	static int a[N];
	static bigint dp[5][N + 1];
	
	while (scanf("%d", &n) == 1){
		pair<int, int> xs[N];
		
		for (int i = 0; i < n; i++){
			scanf("%d", &a[i]);
			xs[i] = make_pair(a[i], -(i + 1));
		}
		
		sort(xs, xs + n);
		
		for (int i = 0; i <= n; i++) for (int k = 0; k < 5; k++) dp[k][i] = 0;
		
		for (int i = 0; i < n; i++){
			add(dp[0], -xs[i].second, 1);
			for (int k = 1; k < 5; k++){
				add(dp[k], -xs[i].second, sum(dp[k - 1], -xs[i].second - 1));
			}
		}
		
		cout << sum(dp[4], n) << endl;
	}
	
	return (0);
}