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 longusing 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;}