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); }