c++ - 我如何使用动态编程解决

Question

这是spoj问题问题的链接

我是解决 Dp 问题的初学者..

虽然我发现了一些模式..但我无法以有效的方式把它放在..

我尝试了天真的方法，但这肯定会给 TLE 。

void cal(int *a,int n)
{
    while(n!=0)
    {
         a[n%10]++;
         n/=10;
    }
}

void print(int *a)
{
    int ans=0;
    for(int i=1;i<=9;i++)
    {
            ans+=i*a[i];
    }
    printf("%d\n",ans);
}

然后从较大的数字中减去较小的数字之和..并添加下限的数字之和..即如果a = 12 b = 15

总和1=51 总和2=66

ans=66-51+(12位数字之和=1+2)=15+3=18

任何帮助都将是有益的..Thanx提前。

Answer 1

我不会为您解决整个问题，而是尝试给您一些提示：

• 不要编写一个计算区间总和[a,b]的函数，而是编写一个计算区间总和的函数，[0,x]而不是：

  SUM([a,b]) = SUM([0, b]) - SUM([0, a-1])
  

• 为了计算到给定限制的数字总和L，对于每个数字d计算它作为一个数字在所有数字中被满足的次数L。为此，请计算d以个位数出现的次数，以十位数出现的次数，依此类推。