今天比赛做得一个数位dp。
首先声明这个题目在数位dp中间绝对是赤裸裸的水题。毫无技巧可言。
题目的意思是个你a和b，要求出在a和b中间有多少个数满足数位上各个数字的和为10的倍数。
显然定义一个二维数组f，f[i][j]表示i位任意的数组合所有数位对10取模后余数为j的种类。
这样直接枚举1-10就可以得出i和i+1的递推关系了呢。简单了吧。
在求答案的时候不是直接求的，用的是数位dp最最经典的答案求法：
那就是定义一个count（x）函数表示不大于x满足的个数，这样，所求的答案就等于count（b）-count（a）了
下面的问题就是如何求得count这个函数值了。
首先我们把数x进行分解，用数组中的一个元素表示x的相对位数的数字。
这样对于从低位开始数起的第i位，如果数位的数值为a[i]，那么我们可以任取0~a[i]-1（想想为什么？这是典型的数位dp的求法），同时保存前面的和并且把a[i]加到和中并取模。
这样如此下去直到求出所有的，同时就是等于x本身的数没有考虑，我们可以直接特判一下就OK了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std; ll f[][],sum[],t,A,B,n,a[],ans,tep; ll count(ll x)
{
if (x<) return;
if (x<) return;
n=ans=tep=;
while (x) a[++n]=x%,x/=;
for (ll i=n; i>; i--)
{
for (ll k=; k<a[i]; k++)
ans+=f[i-][(-(tep+k)%)%];
tep=(tep+a[i])%;
}
for (ll i=; i<=a[]; i++)
if ((i+tep)%==) ans++;
return ans;
} int main()
{
memset(f,,sizeof f);
for (ll i=; i<=; i++) f[][i]=;
for (ll i=; i<=; i++)
{
for (ll j=; j<; j++)
for (ll k=; k<; k++)
f[i+][(j+k)%]+=f[i][j];
}
/*for (int i=1; i<=3; i++)
{
for (int j=0; j<=10; j++) cout<<f[i][j]<<' '; cout<<endl;
}*/
for (ll i=; i<=; i++) sum[i]=f[i][];
cin>>t;
for (ll cas=; cas<=t; cas++)
{
cin>>A>>B;
if (A>B)
{
cout<<"Case #"<<cas<<": "<<<<endl;
continue;
}
/*ll tep=count(B);
cout<<"counting B is: "<<tep<<endl;*/
cout<<"Case #"<<cas<<": "<<count(B)-count(A-)<<endl;
}
return;
} 代码写得十分之挫，而且又很多调试的语句都没有删掉，望谅解。
本人在此最想说的是，dp并不是本题最优解法。
想想对于0-9果断至少有一个加上前面的和是10的倍数。
然后顺着想下去就会发现是如此有趣的规律。我还没想过，但是猜着大概就是这样。
陈兴老师也说了不要用数位dp呢。
呵呵，打个表就知道内在规律，以及解法呢。