HDOJ - 3555 不会按位DP的做法

今天做的一套去年WHU出的多校联合题...这道题纠结了好久才挤出来....去网上搜了下...大牛们似乎都是用的高端的按位DP...我等小菜就只能做屎的想赖推了....

首先将每个位的表打出来...例如sum[3][1]代表100以下的有多少个包含49的数...sum[5][5]代表50000以下有多少包含49的数..首先要看10^k的sum会是多少...也就是sum[k][1]都是多少...其中K从0到10^19 ( 比2^64大的最小位置)....

稍微推一下...譬如知道sum[3][1]=20..也就是1000以内的是20..那么1000 ~ 2000也是20...2000~3000也是20...3000~4000也是20..以此类推..则有20*10个了..然后在4000到5000中还有49XX的没有记入..49XX的一共就是10*10一百个..但是4949会重复计算一次..所以是10*10-1 ( 往大的推会发现这里的 “ 1 " 是sum[i-2][1])...

所以10的阶乘的 sum[i][1]=sum[i-1][1]*10+10^(i-1)-sum[i-2][1]....

然后在1~4时...sum[i][j]=j*sum[i][1]...这个很好想...每一段和 0 ~ 10^i是一样的...有j段就乘以j......

但在5~9时...思想要转过来...因为在4XXXXX ~ 5XXXXX我们又有更多的包含"49"数没有记入...要加上去.则: sum[i][j]=j*sum[i][1]+10^i-sum[i-1][1];

做好了这个表后....下面的工作就轻松多了...但也要注意...

如果简单的 5983 = sum[4][5]+sum[3][9]+sum[2][8]+sum[1][3] 大部分是会对...但交上去会WA..原因是没有考虑本身这个数就含了 " 49" 这种情况..

就拿最浅显的来说 ..49 = sum[2][4] + sum[1][9]...的出来就会是0...再来..493 = sum[3][4]+sum[2][9]+sum[1][3] 得出来也会少...稍微思考一下这种情况也不难处理

如果我扫到了一个49..那么就做完9的sum累加后break...ans+=后面的数+1....如49=sum[2][4]+sum[1][9]+(0+1)..493=sum[3][4]+sum[2][9]+(3+1);这样就能保证万无一失了...

这样做比较费脑细胞...也很费时间...这道题比较正规的方法应该是按位DP...本菜刚才看了好几个文章都没来感觉...慢慢来吧..

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
long long sum[20][12],_10jie[20];
int t,i,n,x;
char s[100];
void Prework()
{
    int i,j;
    long long k=1;
    memset(sum,0,sizeof(sum));
    for (j=5;j<=9;j++) sum[2][j]=1;
    for (i=3;i<=19;i++)
    {
      sum[i][1]=sum[i-1][1]*10+k-sum[i-2][1];
      k*=10;
      for (j=2;j<=4;j++) sum[i][j]=j*sum[i][1];
      for (j=5;j<=9;j++) sum[i][j]=j*sum[i][1]+k-sum[i-1][1];
    }
    _10jie[1]=1;
    for (i=2;i<=19;i++) _10jie[i]=_10jie[i-1]*10;
}
long long  GetAnswer()
{
       int k=1;
       long long ans=0,y=1;
       bool f=false;
       for (i=1;i<=n;i++)
       {
           x=s[i]-'0';
           ans+=sum[n-k+1][x];
           if (x==9)
           {
              if (s[i-1]=='4') { i+=1; f=true; break; }
           }
           k++;
       }
       if (f)
       {     
          y=0;
          for (;i<=n;i++) y=y*10+s[i]-'0';
          ans+=y+1;
       }
       return ans;
}
int main()
{
 //  freopen("B.in","r",stdin);   freopen("B.out","w",stdout);
    Prework();
    scanf("%d",&t);
    while (t--)
    {
       scanf("%s",s+1); n=strlen(s+1); i=1;
       printf("%I64d\n",GetAnswer());
    }
    return 0;
}