题解 UVA12983 【The Battle of Chibi】

· · 题解

本蒟蒻第一次发题解，如有不对之处，欢迎各位dalao指正。

这道题的核心是dp，设f(i,j)表示以序列中第i个为结尾，长度为j的严格上升子序列个数。

那么可以得到

f(i,j)=\begin{cases} 1&j=1\\\sum_{a_k<a_i}f(k,j-1)&j>1\end{cases}

但是转移是O(n)的，所以总时间复杂度为O(n^3),明显超时，所以考虑优化。

可以发现，对于每个f(i,j)都是从某些f(\times,j-1)转移过来的，所以最外层循环可以是j。而转移过来的k<i，那么我们可以联想到前缀和，每次转移要知道在i之前的合法的方案总数，以序列中的元素值为下标，做一个前缀和Sum_{a_i}，表示前i-1个数中a_k<a_i的f(k,j-1)的和，这个前缀和可以用树状数组做，但是因为a_i过大，所以可以用离散化。

这样就可以优化到(nm\times log_2(n))

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int maxn = 1e3 + 5;
const LL MOD = 1e9 + 7;
int n, m;
LL f[maxn][maxn], A[maxn], C[maxn];

LL tmp[maxn], tmp_cnt;

int Key(LL val) {
    int l = 1, r = tmp_cnt;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (tmp[mid] == val) return mid;
        if (tmp[mid] < val) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

inline int lowbit(int x) { return x & -x; }
int ask(int x) {
    LL ret = 0;
    for (; x; x -= lowbit(x)) ret += C[x], ret %= MOD;
    return ret;
}
void add(int x, LL val) {
    for(; x <= tmp_cnt; x += lowbit(x)) C[x] += val, C[x] %= MOD;
}

int main() {
//  freopen("testdata.in", "r", stdin);
//  freopen("testdata.out", "w", stdout);
    int G; scanf("%d", &G);
    for (int T = 1; T <= G; T++) {
        printf("Case #%d: ", T);
        memset(f, 0, sizeof(f));

        scanf("%d%d", &n, &m), tmp_cnt = n;
        for (int i = 1; i <= n; i++) 
            scanf("%lld", &A[i]), tmp[i] = A[i], f[i][1] = 1;
        sort(tmp + 1, tmp + 1 + tmp_cnt);
        tmp_cnt = unique(tmp + 1, tmp + 1 + tmp_cnt) - tmp - 1;

        for (int j = 2; j <= m; j++) {
            memset(C, 0, sizeof(C));
            for (int i = 1; i <= n; i++) {
                int k = Key(A[i]);
                f[i][j] = ask(k - 1), add(k, f[i][j - 1]);
            }
        }
        LL ans = 0;
        for (int i = 1; i <= n; i++) ans = (ans + f[i][m]) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}