本文共 7525 字，大约阅读时间需要 25 分钟。

定义数位dp数组为$f[x][st1][st2]...[stn]$表示第x位状态为$st1...stn$的值。不要把$lim$放到数组里面，因为当lim = 1时，对于每个x只会进入一次。有时候这样能避免dp数组的每次初始化。

Windy定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为2的正整数被称为Windy数。Windy想知道，在A和B之间，包括A和B，总共有多少个 Windy 数？

#include
   
    using namespace std;int f[12][12],digit[12],cnt;int dfs(int x,int st,int op){
     // x为当前为第几位 st为前缀状态 op表示前缀和当前求解的数字的关系，1为相同 0为小于    if(!x)return 1;    if(!op && ~f[x][st])return f[x][st]; // 记忆化    int maxx=op ? digit[x] : 9;    int res=0;    for(int i=0;i<=maxx;++i){
           if(abs(i-st)<2)continue;        if(st==11 && i==0)res+=dfs(x-1,11,op && i==maxx);        else res+=dfs(x-1,i,op && i==maxx);    }    if(!op)f[x][st]=res;    return res;}int solve(int n){
       cnt=1;    while(n){
           digit[cnt++]=n%10;        n/=10;    }    return dfs(cnt-1,11,1)-1;  // -1排除0}int main(){
       memset(f,-1,sizeof f);    int a, b;    while(cin>>a>>b)        cout<
    
     <
    
   

求a和b之间的整数，每个数码出现的数量。

#include
   
    using namespace std;using ll=long long;class DP{
   public:    ll nums;    vector
    
      v;    DP(ll n=-1):nums(n),v(10) {
   }    DP operator+ (const DP &x) const{
           DP res(nums+x.nums);        for(int i=0;i<10;++i)            res.v[i] = v[i] + x.v[i];        return res;    }    DP operator- (const DP &x) const{
           DP res(nums-x.nums);        for(int i=0;i<10;++i)            res.v[i] = v[i] - x.v[i];        return res;    }};DP f[15];int dig[15],cnt;DP dfs(int x,int st,int op){
      // st表示有没有前导零 op表示前缀和要求的数的是否相同    if(!x)return DP(1);    if(!st && !op && ~f[x].nums)return f[x];    int maxx = op ? dig[x] : 9;    DP res(0);    for(int i=0;i<=maxx;++i){
           if(st && i==0){
     // 排除前导零            res = res + dfs(x-1, 1, op && i==maxx);        }else{
               DP tmp = dfs(x-1, 0, op && i==maxx);            res = res + tmp;            res.v[i] += tmp.nums;        }    }    if(!st && !op)f[x] = res;    return res;}DP solve(ll x){
       cnt = 1;    for(int i=0;i<15;++i)        f[i] = DP(-1);    while(x){
           dig[cnt++] = x%10;        x /= 10;    }    return dfs(cnt-1, 1, 1);}int main(){
       ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    ll a,b;    while(cin>>a>>b){
           DP b_ans = solve(b), a_ans = solve(a-1);        DP res = b_ans - a_ans;        for(int i=0;i<10;++i){
               cout<
     
      <<' ';        }        cout<
     
    
   

给出两个数a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

f[x][st][val]，x为当前所在位，st为前缀和数字和，val为前缀值模mod的值。

#include
   
    using namespace std;#define endl '\n'using ll = long long;using pii = pair
    
     ;const int maxn=3e5+3;int mod, dig[20];ll f[20][170][170];ll dfs(int x,int st,int val,int lim){
       if(!x)return st == mod && val == 0;  // 当前缀为mod，值%mod为0时有贡献    if(st>mod)return 0;    if(!lim && ~f[x][st][val])return f[x][st][val];    int maxx = lim ? dig[x] : 9;    ll res=0;    for(int i=0;i<=maxx;++i){
           res += dfs(x-1,st+i,(val*10+i)%mod,lim && i==maxx);    }    if(!lim)f[x][st][val] = res;    return res;}ll solve(ll x){
       ll ans=0;    int cnt=0;    while(x){
           dig[++cnt] = x % 10;        x /= 10;    }    for(int i=1;i<162;++i){
           memset(f,-1,sizeof f);        mod = i;        ans += dfs(cnt, 0, 0, 1);    }    return ans;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    ll a,b;    cin>>a>>b;    cout<
     
      <
     
    
   

当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。比如，1，10，12，212，32122都是 Valley Number。

求不大于N的Valley Number数有多少。 f[x][st][up][ish]，x为当前位，st为上一个数字的值，up为现在是否为递增，ish为现在是否为最高位。

#include
   
    using namespace std;#define endl '\n'using ll = long long;using pii = pair
    
     ;const int maxn=1e2+3;const ll mod=1e9+7;char dig[maxn];int f[maxn][10][2][2],cnt=0;ll dfs(int x,int st,bool up,bool ish,int lim){
       if(x==cnt){
     return 1;}    if(!lim && ~f[x][st][up][ish])return f[x][st][up][ish];    int maxx = lim ? dig[x]-'0' : 9;    ll res = 0;    for(int i=0;i<=maxx;++i){
           if(ish && i==0){
               res = (res+dfs(x+1,9,0,1,lim && i==maxx))%mod;        }else if(up){
               if(i
     
      >T;    while(T--){
           cin>>dig;        cnt = strlen(dig);        memset(f,-1,sizeof f);        cout<
      
       <
      
     
    
   

当数位dp数组中不放lim时，可以只memset一次。

#include
   
    using namespace std;#define endl '\n'using ll = long long;using pii = pair
    
     ;const int maxn=1e2+3;const ll mod=1e9+7;char dig[maxn];int f[maxn][10][2][2],cnt=0;ll dfs(int x,int st,bool up,bool ish,int lim){
       if(x==-1)return 1;    if(!lim && ~f[x][st][up][ish])return f[x][st][up][ish];    int maxx = lim ? dig[x]-'0' : 9;    ll res = 0;    for(int i=0;i<=maxx;++i){
           if(ish && i==0){
               res = (res+dfs(x-1,9,0,1,lim && i==maxx))%mod;        }else if(up){
               if(i
     
      >T;    memset(f,-1,sizeof f);    while(T--){
           cin>>dig;        cnt = strlen(dig);        reverse(dig,dig+cnt);  // 保持f数组下标0为个位        cout<
      
       <
      
     
    
   

求$9e18$范围内，[a,b]之间的数中符合<每个非零数位都能整除这个数>的数的数量。思路：问题可转化为每个非零数位的lcm能整除这个数。由于2520是1-9的lcm，问题转化为每个非零数位的lcm能整除这个数取模2520.

f[x][st][op]，x为当前位，st为前缀lcm，op为当前的前缀取模2520. 特殊：由于f数组和lim无关，所以在不同次查询中都能用！只要初始化一次！ 否则会超时。

#include
   
    using namespace std;//#define endl '\n'using ll = long long;using pii = pair
    
     ;const int maxn=1e2+3;const ll mod = 2520;int arr[][4]={
   {
   1,2,4,8},{
   1,3,9},{
   1,5},{
   1,7}}, na[]={
   4,3,2,2};ll f[20][50][2523];int dig[20],ma[2523];vector
     
       num;int gcd(int a,int b){
       return a%b ? gcd(b,a%b) : b;}void init(int x,int now){
       if(x&4){
   num.push_back(now);return;}    for(int i=0;i
      
       >T;    while(T--){
           ll a,b;        cin>>a>>b;        cout<
       
        <
       
      
     
    
   

题意：对于一个数$i$，把它看成$k$进制数，把所有位上的数移动到一个位上，代价是移动的石子数量 × 移动的距离。问把$[L,R]$内每个数都进行一次合并，求最小合并代价。

思路：先假设所有数都合并到个位，很容易能得到总代价。然后考虑移动。当一个n位数的 $sum[n...i]>sum[i-1...1]$ 时，它合并到的点必然$\ge i$，所以并且代价应该减少$sum[n...i]-sum[i-1...1]$。所以可以贪心一位一位进行数位DP。

#include
   
    using namespace std;//#define endl '\n'#define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)typedef long long LL;const int N = 5e4 + 5, K = 105;const int inf = 1e9;const long long mod = 1e9 + 7;using LD = long double;using LL = long long;using PII = pair
    
     ;/** long long !!!* array size !!!*/int dig[1005];LL f[105][1505], pos, k;LL dfs(int x, int st, int lim){
       if(pos > 1 && st < 0)return 0;    if(!x)return st;    if(!lim && ~f[x][st])return f[x][st];    int maxx = lim ? dig[x] : k - 1;    LL res = 0;    for(int i = 0; i <= maxx; ++i){
           if(pos == 1)res += dfs(x-1, st + i * (x - 1), lim && i == dig[x]);        else if(x >= pos)res += dfs(x-1, st + i, lim && i == dig[x]);        else res += dfs(x-1, st - i, lim && i == dig[x]);    }    if(!lim)f[x][st] = res;    return res;}LL solve(LL n){
       int cnt = 0;    while(n){
           dig[++cnt] = n % k;        n /= k;    }    pos = 1;    memset(f, -1, sizeof(f));    LL ans = dfs(cnt, 0, 1);    for(pos = 2; pos <= cnt; ++pos){
           memset(f, -1, sizeof(f));        //cout << ans << endl;        ans -= dfs(cnt, 0, 1);    }    return ans;}int main(){
       IOS;    LL l, r;    cin >> l >> r >> k;    cout << solve(r) - solve(l - 1) << endl;}
    
   

转载地址：http://rgkzi.baihongyu.com/