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

​​传送门​​

f[i][j] 表示1--i 选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;
}