UVA12983 The Battle of Chibi

第一眼能看出来是个dp

O($n^3$) 暴力应该很好想 dp[i][j] = $sum_{k=1}^i [a[k] < a[i]] *dp[k][j-1]$

发现dp[i][j] 为前面小于它的数长度为j-1的总和,用树状数组前缀和优化一下搞成$O(n^2log_n)$

先离散化,dp时先枚举位置,再枚举上升序列的长度

树状数组要开二维哦,打代码的时候发现dp数组可以用树状数组直接代替(小小的空间优化)

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
const int P = 1e9+7;
int read(void) {
    int x = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x;
}
int T,n,m;
int a[N];
struct node{
    int pos,val;
    bool operator < (const node &i) const {
        if (val == i.val) return pos < i.pos;
        return val < i.val;
    }
}p[N];
bool cmp(node i,node j) {
    return i.pos < j.pos;
}
long long d[N][N];
inline int low(int x) {
    return x & -x;
}
int sum(int x,int p) {
    long long val = 0;
    for (;x;x -= low(x)) val += d[p][x];
    return val % P;
}
void add(int x,int k,int p) {
    for (;x <= n; x += low(x)) d[p][x] = (d[p][x] + k) % P;
}
int main() {
    T = read();
    int cnt = 0;
    while (T--) {
        cnt++;
        n = read(),m = read();
        for (int i = 1;i <= n; i++) p[i] = (node){i,read()};
        sort(p + 1,p + n + 1);
        int x = 0,k = 0;
        for (int i = 1;i <= n; i++) {
            if (x == p[i].val) 
                p[i].val = k;
            else {
                x = p[i].val;
                p[i].val = i;
                k = i;
            }
        }
        sort(p + 1,p + n + 1,cmp);
        memset(d,sizeof(d));
        long long ans = 0;
        for (int i = 1;i <= n; i++) {
            add(p[i].val,1,1);
            for (int j = 2;j <= m; j++) {
                int k = sum(p[i].val-1,j-1);
                add(p[i].val,k,j);
                if (j == m) ans = (ans + k) % P;
            }
        }
        if (m == 1) ans += n;
        printf ("Case #%d: %lldn",cnt,ans % P);
    }
    return 0;
}