noip 2010 数字统计

数位dp解水题

dp[i][j]表示 有i位，且首位是j(包括0) 的 ‘2’的个数 
dp[i][j]={
　　　　　　　　Σ（dp[i-1][k]）,j!=2;
　　　　　　　　Σ（dp[i-1][k]）+val[i],j!=2;
　　　　　　}
其中val[i]为，十进制下，第i位的权值，
在这里可以当作 如果 j是2 那会多计数几次来使用

令 work(x) 表示 0~x-1 中 '2' 的个数
目标 work(r+1)-work(l);
work()注意 
在累加dp[i][j]的同时，统计之前出现了几次‘2’，记为t；
每次再加上t*val[i];

 #include<bits/stdc++.h>

 using namespace std;

 int len,dp[][],digit[],l,r;

 int val[]={,,,,,,,};

 //dp[i][j]表示 有i位，且首位是j 的 ‘2’的个数

 void init(){

     dp[][]=;

     for(int i=;val[i]<=r;i++)

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

             for(int k=;k<=;k++)

                 dp[i][j]+=dp[i-][k];

             if(j==)dp[i][j]+=val[i];

         }

 }

 int work(int x){

     len=;

     for(;x;x/=)digit[++len]=x%;

     digit[len+]=;

     int ret=,t=;

     for(int i=len;i;i--){

         if(digit[i+]==)t++;

         for(int j=;j<digit[i];j++)

             ret+=dp[i][j]+t*val[i];

     }

     return ret;

 }

 int main(){

     cin>>l>>r;

     init();

     cout<<work(r+)-work(l);

     return ;

 }

巴特西

noip 2010 数字统计

最新文章

热门文章