国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > [数位dp] spoj 10738 Ra-One Numbers

[数位dp] spoj 10738 Ra-One Numbers

来源:程序员人生   发布时间:2014-10-06 08:00:01 阅读次数:2392次

题意:给定x、y,为[x,y]之间有多少个数的偶数位和减去奇数位和等于一。

个位是第一位。

例子: 10=1-0=1 所以10是这样的数

思路:数位dp[i][sum][ok] i位和为sum 是否含有前导0.

然后就是因为有负数 所以根据范围把0设置为100 然后最后和等于101则为所求的数。

代码:

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. #include"cstdlib" 
  2. #include"cstdio" 
  3. #include"cstring" 
  4. #include"cmath" 
  5. #include"stack" 
  6. #include"algorithm" 
  7. #include"iostream" 
  8. using namespace std; 
  9. int dp[12][200][2],num[12]; 
  10. int fuck[2]={1,-1}; 
  11. int dfs(int site,int sum,int ok,int f) 
  12.     if(site==0) 
  13.     { 
  14.         if(ok==0) return 0; 
  15.         return sum==101?1:0;  //小处理 和为101 
  16.     } 
  17.     if(!f&&dp[site][sum][ok]!=-1) return dp[site][sum][ok]; 
  18.     int len=f?num[site]:9; 
  19.     int ans=0; 
  20.     for(int i=0;i<=len;i++) 
  21.     { 
  22.         if(ok==0) 
  23.         { 
  24.             if(i==0) ans+=dfs(site-1,sum,ok||i!=0,f&&i==len); 
  25.             else ans+=dfs(site-1,sum+i*fuck[site%2],ok||i!=0,f&&i==len); 
  26.         } 
  27.         else 
  28.         { 
  29.             ans+=dfs(site-1,sum+i*fuck[site%2],ok||i!=0,f&&i==len); 
  30.         } 
  31.     } 
  32.     if(!f) dp[site][sum][ok]=ans; 
  33.     return ans; 
  34. int solve(int x) 
  35.     if(x<0) return 0; 
  36.     int cnt=0; 
  37.     while(x) 
  38.     { 
  39.         num[++cnt]=x%10; 
  40.         x/=10; 
  41.     } 
  42.     return dfs(cnt,100,0,1);  //进入的时候 sum=100 
  43. int main() 
  44.     int t; 
  45.     scanf("%d",&t); 
  46.     memset(dp,-1,sizeof(dp)); 
  47.     while(t--) 
  48.     { 
  49.         int x,y; 
  50.         scanf("%d%d",&x,&y); 
  51.         printf("%d ",solve(y)-solve(x-1)); 
  52.     } 
  53.     return 0; 

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生