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

​​传送门​​

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

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

#include#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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。