hdu 4352 数位dp+nlogn的LIS

题意：求区间L到R之间的数A满足A的的数位的最长递增序列的长度为K的数的个数。

链接：点我

该题的关键是记录LIS的状态，学习过nlogn解法的同学都知道，我们每次加入的元素要和前面的比对替换，这里就用了这个方法

比如1 3 6，用二进制表示为001000101，假如新加入的数为2，那么我们枚举比2大的数，观察是否存在，这里找到3，我们把3替换成2，状态变成1,2,6

不懂的童鞋可以看这里的nlogn的介绍：点我

还有就是注意前导0

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 typedef long long ll;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt,K;

 ll dp[][<<][];

 int digit[];

 int k;

 ll getst(ll s,ll u,ll& xx)  // 状态转移

 {

     ll i,ss;

     for(i=u;i<;i++)

     {

         if(s&(<<i)) break ;    //有比u大的，替换掉

     }

     if(i<)

     {

         ss=s^(<<i);

         ss=ss^(<<u);

     }

     else    //没有比u大的，u放入s中

     {

         xx++;

         ss=s^(<<u);

     }

     return ss;

 }

 ll dfs(int p,ll s,ll len,int fl,bool e) {    //位置，lis状态，lis长度，前导0

     if (p==-) return len==k;

     if (!e &&dp[p][s][k]!=-) return dp[p][s][k];

     ll res = ;

     int u=e?digit[p]:;

     for (int i=;i<=u;++i)

     {

         ll ns,nlen=len;

         if(fl==&&i==) ns=;

         else    ns=getst(s,i,nlen);

         res+=dfs(p-,ns,nlen,fl||i!=,e&&i==u);

     }

     return e?res:dp[p][s][k]=res;

 }

 ll solve(ll n)

 {

     int len=;

     while(n)

     {

         digit[len++]=n%;

         n/=;

     }

     return dfs(len-,,,,);

 }

 int main()

 {

     int i,j;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     scanf("%d",&tt);

     int ca=;

     memset(dp,-,sizeof(dp));

     while(tt--)

     {

         ll l,r;

         scanf("%I64d%I64d%I64d",&l,&r,&k);

         ll ans=solve(r)-solve(l-);

         printf("Case #%d: %I64d\n",++ca,ans);

     }

 }

巴特西

hdu 4352 数位dp+nlogn的LIS

最新文章

热门文章