HDU 4352：XHXJ's LIS

题目：（原题是英文而且很迷）求区间内数的LIS长度==k的个数，比如153948的LIS为1 3 4 8，长度为4。据说这种题叫DP中DP，本来是线性，再套一层状压+数位，简直厉害到不行……

线性的部分为O（nlogn）的LIS。比如现在找出的序列为1 3 4 8，两个策略，如果再来一个2就变成1 2 4 8（二分找第一个比它大的数），再来9就变成1 2 4 8 9（更新长度）。代码在下面

 #include<cstdio>

 #include<ctime>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int n,f[],x,l,r,len;

 int main()

 {

     scanf("%d",&n);

     f[]=-;

     for(int i=;i<=n;++i){

         scanf("%d",&x);

         l=;r=len;

         if(x>f[len]){

             f[++len]=x;

             continue;

         }

         while(l<r){

             int mid=(l+r)>>;

             if(x>f[mid]) l=mid+;

             else r=mid;

         }

         f[l]=x;

     }

     printf("%d",len);

     return ;

 }

然后我们就要数位里状压了。我们知道对于0~9的LIS最长是10，那就可以用二进制来表示LIS的状态。还用上面的例子1 3 4 8，表示为0100011010。然后dp的时候发现状态的更新并没有那么方便，不过我们可以预处理LIS的更新情况，建立状态之间的联系，比如1 3 4 8--插入2-->1 2 4 8。之后直接套进数位DP的板子就做完了，并没有看起来那么难。

 #include<cstdio>

 #include<cmath>

 #include<ctime>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #define ll long long

 using namespace std;

 const int base=<<;

 int k,siz[base],dig[base],ne[base][];

 ll f[][base][];

 ll dfs(int w,int sta,bool o,bool pd)

 {

     if(!w) return siz[sta]==k;

     if((!pd)&&(f[w][sta][k]!=-)) return f[w][sta][k];

     ll up=pd?dig[w]:,tmp();

     for(int i=;i<=up;++i) tmp+=dfs(w-,(o&(!i))?:ne[sta][i],o&(!i),pd&(i==up));

     if(!pd) f[w][sta][k]=tmp;

     return tmp;

 }

 ll F(ll num)

 {

     int wei();

     while(num){

         dig[++wei]=num%;

         num/=;

     }

     return dfs(wei,,,);

 }

 int fnd(int i,int num)

 {

     for(int j=num;j<;++j) if(i&(<<j)) return i^(<<j)|(<<num);

     return i|(<<num);

 }

 int main()

 {

     ll T,l,r;

     memset(f,-,sizeof(f));

     for(int i=;i<base;++i){

         for(int j=;j<;++j){

             if(i&(<<j)) siz[i]++;

             ne[i][j]=fnd(i,j);

         }

     }

     scanf("%d",&T);

     for(int i=;i<=T;++i){

         scanf("%lld%lld%d",&l,&r,&k);

         printf("Case #%d: %lld\n",i,F(r)-F(l-));

     }

     return ;

 }

巴特西

HDU 4352：XHXJ's LIS

最新文章

热门文章