[原创]vijos P2026 几乎奇偶等和数 [数位dp]【动态规划】

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
const int N   = 1e7+7;
const int MOD = 998244353;
const double eps = 1e-6;
# define rep(aa,bb,cc) for(int aa=(bb),ee=(cc);aa<=ee;aa++)
# define abs(x)        ((x)>0?(x):-(x))
/*********************************************/

int num[10],len;
int dp[10][120][10][10][10];
//数位 奇位和与偶位和的差 对差的影响的正值 对差的影响的负值 
int dfs(int pos,int sub,int posi,int nop,bool limit,int bt){
    if(pos<0) return bt%2==0 && sub!=0 && (sub*(sub+posi)<=0||sub*(sub-nop)<=0);
    int &d = dp[pos][sub+60][posi][nop][bt];
    if(!limit && d!=-1) return d;

    int endi=9;if(limit) endi=num[pos];

    int res = 0;
    for(int i=0;i<=endi;i++){
        if(bt == 0){
            if(i == 0)   res+=dfs(pos-1,0,0,0,0,0);
            else {
                if(bt&1) res+=dfs(pos-1,sub+i,9-i,i-1,limit&&i==endi,1);
                else     res+=dfs(pos-1,sub-i,i-1,9-i,limit&&i==endi,1);
            }
        }
        else {
            if(bt&1) res += dfs(pos-1,sub+i,max(posi,9-i),max(nop,i),limit&&i==endi,bt+1);
            else     res += dfs(pos-1,sub-i,max(posi,i),max(nop,9-i),limit&&i==endi,bt+1);
        }
    }
    if(!limit) d = res;
    return res;
}
int cal(int x){
    if(x<=0) return 0;
    for(len = 0;x;x/=10) num[len++]=x%10;
    return dfs(len-1,0,0,0,1,0);
}
int x,y;
int main(){
    memset(dp,-1,sizeof(dp));
    while(~scanf("%d%d",&x,&y)){
        printf("%d\n",cal(y)-cal(x-1));
    }
    return 0;
}