UVA12983The Battle of Chibi

很容易想到（n^3）的DP：

定义：f[i][j]表示前j个数构成的以j为结尾的数列中，长度为i的严格递增子序列的个数。

for(int i=1;i<=m;i++)
    for(int j=i;j<=n;j++)
        for(int k=0;k<j;k++)
            if(a[k]<a[j])
                f[i][j]=(f[i][j]+f[i-1][k])%mod;
int ans=0;
for(int i=1;i<=n;i++)
    ans=(ans+f[m][i])%mod;

下面我们来想该怎样优化:

首先看到这个数据比较大，应该会想到离散化一下。

a[0].x=-INF,a[0].id=1;
for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i+1;
sort(a,a+n+1,cmp);
for(int i=0;i<=n;i++)b[i]=a[i].id;

然而由a[k]<a[j]就很容易想到用树状数组来优化。

将f[i]的树值先用树状数组存下，需要的时候直接求和，然后求出在读入

具体代码如下：

f[0][0]=1;
for(int i=1;i<=m;i++){
    memset(c,0,sizeof(c));
    add(b[0],f[i-1][0]);
    for(int j=1;j<=n;j++){
        f[i][j]=ask(b[j]-1);
        add(b[j],f[i-1][j]);
        }
}

再给个完整代码吧：

#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
struct note{
    int x,id;
}a[1010];
int T,n,m;
long long c[1010],f[1010][1010],ans,mod=1000000007;
int b[1010];
bool cmp(note aa,note bb){return (aa.x==bb.x?aa.id>bb.id:aa.x<bb.x);}

////////////////////////////树状数组的操作
int lowbit(int x){return x&(-x);};
void add(int x,int k){for(int i=x;i<=n+1;i+=lowbit(i))c[i]=(c[i]+k)%mod;}
long long ask(int x){long long sum=0;for(int i=x;i>0;i-=lowbit(i))sum=(sum+c[i])%mod;return sum;}
////////////////////////////

int main(){
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        scanf("%d%d",&n,&m);
        memset(f,0,sizeof(f));
        ans=0;

        ////////////////////////////离散化操作
        a[0].x=-INF,a[0].id=1;
        for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i+1;
        sort(a,a+n+1,cmp);
        for(int i=0;i<=n;i++)b[i]=a[i].id;
        ////////////////////////////

        f[0][0]=1;
        for(int i=1;i<=m;i++){
            memset(c,0,sizeof(c));
            add(b[0],f[i-1][0]);
            for(int j=1;j<=n;j++){
                f[i][j]=ask(b[j]-1);
                add(b[j],f[i-1][j]);
            }
        }
        for(int i=1;i<=n;i++)ans=(ans+f[m][i])%mod;
        printf("Case #%d: %lld\n",t,ans);
    }
    return 0;
}

结束语：

多组数据需注意，memeset别忘记。

树状数组留意0，否则就要TLE。