The Battle of Chibi[树状数组+DP]

传送门

f[i][j] 表示1--i 选j个的情况 

先离散化 , 然后开n个树状数组分别维护 f[][j]  

#include<bits/stdc++.h>
#define N 1005
#define Mod 1000000007
#define LL long long
using namespace std;
int T,n,m,a[N],b[N];
LL f[N][N],c[N][N],ans;
LL Q(int u,int x){LL ans=0; for(;x;x-=x&-x) ans=(ans+c[u][x])%Mod; return ans;
}
void Up(int u,int x,int val){for(;x<=n;x+=x&-x) c[u][x]=(c[u][x]+val)%Mod;
}
int main(){scanf("%d",&T); for(int I=1;I<=T;I++){memset(c,0,sizeof(c));memset(f,0,sizeof(f)); ans=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]); b[i]=a[i];}sort(b+1,b+n+1);int siz = unique(b+1,b+n+1) - (b+1);for(int i=1;i<=n;i++){a[i] = lower_bound(b+1,b+siz+1,a[i])-b;}for(int i=1;i<=n;i++){f[i][1]=1 , Up(1,a[i],1); if(m==1) ans++;for(int j=2;j<=m;j++){f[i][j] = Q(j-1 , a[i]-1);Up(j , a[i] , f[i][j]);if(j==m) ans = (ans + f[i][j])%Mod;}}printf("Case #%d: %lld\n",I,ans);}return 0;
}