[數(shù)位dp] spoj 10738 Ra-One Numbers
來源：程序員人生 發(fā)布時間：2014-10-06 08:00:01 閱讀次數(shù)：2553次
題意：給定x、y，為[x,y]之間有多少個數(shù)的偶數(shù)位和減去奇數(shù)位和等于一。
個位是第一位。
例子： 10=1-0=1 所以10是這樣的數(shù)
思路：數(shù)位dp[i][sum][ok] i位和為sum 是否含有前導0.
然后就是因為有負數(shù) 所以根據(jù)范圍把0設置為100 然后最后和等于101則為所求的數(shù)。
代碼：
- #include"cstdlib"
- #include"cstdio"
- #include"cstring"
- #include"cmath"
- #include"stack"
- #include"algorithm"
- #include"iostream"
- using namespace std;
- int dp[12][200][2],num[12];
- int fuck[2]={1,-1};
- int dfs(int site,int sum,int ok,int
f)
- {
- if(site==0)
- {
- if(ok==0)
return 0;
- return sum==101?1:0;
- }
- if(!f&&dp[site][sum][ok]!=-1)
return dp[site][sum][ok];
- int len=f?num[site]:9;
- int ans=0;
- for(int i=0;i<=len;i++)
- {
- if(ok==0)
- {
- if(i==0) ans+=dfs(site-1,sum,ok||i!=0,f&&i==len);
- else ans+=dfs(site-1,sum+i*fuck[site%2],ok||i!=0,f&&i==len);
- }
- else
- {
- ans+=dfs(site-1,sum+i*fuck[site%2],ok||i!=0,f&&i==len);
- }
- }
- if(!f) dp[site][sum][ok]=ans;
- return ans;
- }
- int solve(int x)
- {
- if(x<0) return 0;
- int cnt=0;
- while(x)
- {
- num[++cnt]=x%10;
- x/=10;
- }
- return dfs(cnt,100,0,1);
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- memset(dp,-1,sizeof(dp));
- while(t--)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- printf("%d
",solve(y)-solve(x-1));
- }
- return 0;
- }
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
