UVA12983 The Battle of Chibi【题解】数据结构优化DP

题面：https://www.luogu.org/problem/UVA12983

求数列有多少个长度为m的严格上升子序列。

暴力很好打，牛客网竟然过了。

f[i][j]表示到第j位匹配了长度为i的严格上升子序列。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,num;
namespace work{
const int mod=1e9+7;
int n,m,a[1006],f[1006][1006];
int main(){
    memset(f,0,sizeof(f));
    a[0]=-(1<<30);
    f[0][0]=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<j;k++)
                if(a[j]>a[k])
                    f[i][j]=(f[i][j]+f[i-1][k])%mod;
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+f[m][i])%mod;
    return ans;
}
}
int main()
{
    scanf("%d",&t);
    while(t--){
        num++;
        printf("Case #%d: %d
",num,work::main());
    }
    return 0;
}

果然过不了n²m的复杂度很尴尬。

那么尝试用数据结构优化。

发现，其实每向后一位就只多了一个决策点。

那么其实就可以用数据结构来插入和求前缀和。

可以用树状数组。

那么就是每次更新决策点到树状数组里，然后查询出编号小的前缀和。

这时候f[i][j]表示到i找到长度为j的上升子序列的个数。

而且因为树状数组无法处理0，所以n++。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int num,t;
const int maxn=1030,mod=1e9+7;
namespace work{
int n,m;
struct node{
    int w,id;
    bool operator < (const node &x) const{
        return w<x.w;
    }
}a[maxn];
int pos[maxn],c[maxn],f[maxn][maxn];
inline void add(int x,int y){
    for(;x<=n;x+=(x&-x))
        c[x]=(c[x]+y)%mod;
}
inline int ask(int x){
    int ans=0;
    for(;x;x-=(x&-x))
        ans=(ans+c[x])%mod;
    return ans;
}
int main(){
    memset(f,0,sizeof(f));
    scanf("%d%d",&n,&m);
    n++;
    for(int i=2;i<=n;i++)
        scanf("%d",&a[i].w),a[i].id=i;
    sort(a+2,a+1+n);
    for(int i=2;i<=n;i++)
        pos[a[i].id]=i;
    pos[1]=1;
    add(1,1);
    for(int j=1;j<=m;j++){
        for(int i=2;i<=n;i++){
            f[i][j]+=ask(pos[i]);
            f[i][j]%=mod;
            add(pos[i],f[i][j-1]);
        }
        memset(c,0,sizeof(c));
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+f[i][m])%mod;
    return ans;
}
}
int main()
{
    scanf("%d",&t);
    while(t--){
        num++;
        printf("Case #%d: %d
",num,work::main());
    }
    return 0;
}