$HDOJ\ The\ Battle\ of\ Chibi$ 数据结构优化$DP$

 1 #include<bits/stdc++.h>
 2 #define il inline
 3 #define Rg register
 4 #define go(i,a,b) for(Rg int i=a;i<=b;i++)
 5 #define yes(i,a,b) for(Rg int i=a;i>=b;i--)
 6 #define mem(a,b) memset(a,b,sizeof(a));
 7 #define int long long
 8 using namespace std;
 9 il int read()
10 {
11     int x=0,y=1;char c=getchar();
12     while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();}
13     while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();}
14     return x*y;
15 }
16 const int N=1010,mod=(1e9)+7;
17 int T,n,n1,m,as,a[N],b[N],v[N],c[N],f[N][N];
18 il int Find(int x){return find(b+1,b+n1+1,x)-b;}//find(b+1,b+n1+1,x)-b;}
19 il int lowbit(int x){return x&(-x);}
20 il void add(int p,int w){while(p<=n1){c[p]=(c[p]+w)%mod;p+=lowbit(p);}}
21 il int sum(int p){int ret=0;while(p){ret=(ret+c[p])%mod;p-=lowbit(p);}return ret%mod;}
22 main()
23 {
24     T=read();
25     go(TT,1,T)//remember to init
26     {
27         n=read(),m=read();
28         go(i,1,n)a[i]=b[i]=read();
29         sort(b+1,b+n+1);
30         n1=unique(b+1,b+n+1)-(b+1);
31         go(i,1,n){v[i]=Find(a[i]);}
32         f[0][0]=1;
33         go(i,1,m)
34         {
35             mem(c,0);if(i==1)add(1,1);
36             go(j,1,n)f[i][j]=sum(v[j]),add(v[j]+1,f[i-1][j]);
37         }
38         as=0;go(i,1,n)as=(as+f[m][i])%mod;
39         printf("Case #%lld: %lld\n",TT,as);
40     }
41     return 0;
42 }