hdu 3943 经典数位dp好题

/*

题意:求出p-q的第j个nya数

数位dp，求出p-q的所有nya数的个数很好求，但是询问求出最终那个第j个值时是我不会求了看了下别人的思路

具体就是把p-q的第j个转化成0-q的第low+j个（其中low为小于等于p的nya数）

枚举q的每一位数字，枚举位数值并进行比较直至求出每一位的值。

经典好题，长见识了。

*/

#include<stdio.h>

#include<string.h>

#define ll __int64

#define N   21

ll dp[N][N][N][2],x,y,ans;//多开一个ok加快速度，把所有解全存起来

ll digit[N],flen;//flen吧最终q的长度保存起来

ll dfs(ll len,ll sin,ll qin,ll ok) {

 if(!len) {

    if(sin==x&&qin==y)return 1;

    return 0;

 }

 if(sin>x||qin>y)return 0;

 if(dp[len][sin][qin][ok]!=-1)

    return dp[len][sin][qin][ok];

 ll ans=0,maxx=ok?digit[len]:9,i;

 for(i=0;i<=maxx;i++)

    ans+=dfs(len-1,sin+(i==4),qin+(i==7),ok&&i==maxx);

 dp[len][sin][qin][ok]=ans;//把所有情况保存起来

 return ans;

}

ll f(ll n) {

  ll len=0;

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

  while(n) {

     digit[++len]=n%10;

     n/=10;

  }

  flen=len;//在询问时会用到

  return dfs(len,0,0,1);

}

void  dfs_answer(ll len,ll sin,ll qin,ll ok,ll kth) {//不断的递归调用自身直至求出最终结果

  ll cnt,maxx=ok?digit[len]:9,i;

  for(i=0;i<=maxx;i++)  {

     cnt=dfs(len-1,sin+(i==4),qin+(i==7),ok&&i==maxx);

  if(cnt<kth)

    kth-=cnt;

  else

    break;

  }

  ans=ans*10+i;//说明当第len个数是i时存在结果，求出的是第len位的值

  if(len!=1)

    dfs_answer(len-1,sin+(i==4),qin+(i==7),ok&&i==maxx,kth);//不断递归调用本身，顶多调用20次，每次的时间复杂度为0（1）,因为每次调用dfs时的结果都已经保存起来了

}

int main() {

  ll t,m,n,j,k,kk=0,q,low,high;

  scanf("%I64d",&t);

  while(t--) {

    scanf("%I64d%I64d%I64d%I64d",&n,&m,&x,&y);

     low=f(n);//求出0-n的nya数个数

     high=f(m);//求出0-m的nya数个数

     k=high-low;//n-m之间的个数

     scanf("%I64d",&q);

     printf("Case #%I64d:\n",++kk);

     while(q--) {

        scanf("%I64d",&j);

        if(j>k)

            printf("Nya!\n");

         else {

             ans=0;

             j+=low;//计算0-m的第j个nya数

             dfs_answer(flen,0,0,1,j);

           printf("%I64d\n",ans);

         }

     }

  }

return 0;}
巴特西

hdu 3943 经典数位dp好题

最新文章

热门文章
