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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

$AcWing$

$Description$

$Sol$

首先显然是是以严格递增子序列的长度为阶段,由于要单调递增,所以还要记录最后一位的数值

$F[i][j]$表示前$i$个数中以$A_i$结尾的长度为j单调递增序列有多少个

$F[i][j]=\sum_{k<i且A_k<A_i}^{ }F[k][j-1]$

注意到,如果没有$A_k<A_i$这个条件我们就可以直接维护前缀和了

有$A_k<A_i$这个条件,可以考虑维护$A_i$为下标,$F[i][j-1]$为值的数组的前缀和

$A_i$的值会过大而不能作为下标,要离散化

但是$i$每增加$1$,这个数组并不像之前那样简单的在数组后面加一个值,而是在不确定的地方修改,这样的话如果再是朴素地维护前缀和也起不到上面优化的作用了

待修改的区间求和问题$???$树状数组$!!!$

也就是说维护一个以$A_i$的离散值为下标,$F[i][j-1]$为值的树状数组就好啦

然后讲下细节(敖丙说了细节决定成败$qwq$).就是初始化是$f[0][0]=1$,但是众所周知树状数组的下标不可以为$0$,所以把整个树状数组往右移一位.

$Code$

 #include<bits/stdc++.h>

 #define il inline

 #define Rg register

 #define go(i,a,b) for(Rg int i=a;i<=b;i++)

 #define yes(i,a,b) for(Rg int i=a;i>=b;i--)

 #define mem(a,b) memset(a,b,sizeof(a));

 #define int long long

 using namespace std;

 il int read()

 {

     int x=,y=;char c=getchar();

     while(c<''||c>''){if(c=='-')y=-;c=getchar();}

     while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

     return x*y;

 }

 const int N=,mod=(1e9)+;

 int T,n,n1,m,as,a[N],b[N],v[N],c[N],f[N][N];

 il int Find(int x){return find(b+,b+n1+,x)-b;}//find(b+1,b+n1+1,x)-b;}

 il int lowbit(int x){return x&(-x);}

 il void add(int p,int w){while(p<=n1){c[p]=(c[p]+w)%mod;p+=lowbit(p);}}

 il int sum(int p){int ret=;while(p){ret=(ret+c[p])%mod;p-=lowbit(p);}return ret%mod;}

 main()

 {

     T=read();

     go(TT,,T)//remember to init

     {

         n=read(),m=read();

         go(i,,n)a[i]=b[i]=read();

         sort(b+,b+n+);

         n1=unique(b+,b+n+)-(b+);

         go(i,,n){v[i]=Find(a[i]);}

         f[][]=;

         go(i,,m)

         {

             mem(c,);if(i==)add(,);

             go(j,,n)f[i][j]=sum(v[j]),add(v[j]+,f[i-][j]);

         }

         as=;go(i,,n)as=(as+f[m][i])%mod;

         printf("Case #%lld: %lld\n",TT,as);

     }

     return ;

 }