题解 P7682

· · 题解

这题难度是不是稍微有点问题。

数位 DP 咋可能是黄题呢？

(如果有什么不用数位 DP 的方法当我没说)。

首先有几个很明显的特征，它的数据范围经常是 10^9 ~ 10^{18}。

另外一个是区间查询。

我们可以考虑用前缀和一样的思路求出 [1,n] 之间的数的和，然后减去 [1,l) 即可。

我写的是记忆化搜索版本，对着每一位都枚举一下。

注意一下上限，以及要记录的前一个数的值，连续数的数量以及总和 (这边内存倒是不会爆掉，但应该有比我更优内存的)。

然后就是一道模板数位 DP 了。

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int INFN=2035;
const int INF=17;
const int INFF=13;
int l,r,a[INF],tot,f[INF][INFF][INF][INFN];
// 第几位，有没有卡着上限，前一个数，连续的数多少个，总和多少？
int DFS(int b,int c,int d,int e,int p) {
        if (b<=0) return p+d*e*e;
        if (f[b][d][e][p]!=-1 && !c) return f[b][d][e][p];
        int Max=(c ? a[b] : 9),sum=0;
        for (int i=0; i<=Max; i++) {
                sum+=DFS(b-1,(c && i==Max),i,(i==d ? e+1 : 1),(i!=d ? p+d*e*e : p));
        }
        if (!c) f[b][d][e][p]=sum;
        return sum;
}
int calc(int xx) {
        memset(f,255,sizeof f);
        memset(a,0,sizeof a); tot=0;
        while (xx) {
                a[++tot]=xx%10;
                xx/=10;
        }
        return DFS(tot,1,10,0,0);
}
signed main()
{
        scanf("%lld %lld",&l,&r);
        cout<<calc(r)-calc(l-1)<<"\n";
        return 0;
}

谢谢观赏。