定义DP[pos][pre][odd][even]，pos代表当前数位，pre代表前一位的数值，odd代表到前一位连续的奇数个数，even代表到前一位连续偶数个数。
odd和even肯定至少有一个为0，而且最后的判断只和odd与even的奇偶性有关，能看出这个状态是可以被缩小到很小的，但是DP菜鸟我为了避免出错，还是定义了8万的可以接受的数组。
代码及注释如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define LL long long LL dp[20][10][20][20]; int bit[20]; LL dfs(int pos,int pre,bool limit,bool lead0,int odd,int even) { if(pos == -1) { if(odd==0 && even%2==1) return 1; if(even==0 && odd%2==0) return 1; return 0; } if(!limit && !lead0 && dp[pos][pre][odd][even]!=-1)///为了 ///保证没有任何的歧义，前两个判定条件是必要的 { return dp[pos][pre][odd][even]; } int up = limit? bit[pos]: 9; LL ans = 0; for(int i = 0; i <= up; i++) { bool Nlimit = (limit && i==up); bool Nlead0 = (lead0 && i==0); if(lead0)///前导0存在的时候，建议特殊判断 { if(i==0) ans += dfs(pos-1,i,Nlimit,Nlead0,0,0); else if(i%2==0) ans += dfs(pos-1,i,Nlimit,Nlead0,0,1); else ans += dfs(pos-1,i,Nlimit,Nlead0,1,0); } else { if( (odd%2==1&&i%2==0) || (even!=0&&even%2==0&&i%2==1) ) continue; ///这两种状态是不符合要求的状态，第二个判断需要注意even = 0的情况 if(i%2==0) ans += dfs(pos-1,i,Nlimit,Nlead0,0,even+1); else ans += dfs(pos-1,i,Nlimit,Nlead0,odd+1,0); } } if(!limit && !lead0) dp[pos][pre][odd][even] = ans; return ans; } LL solve(LL x) { int pos = 0; while(x) { bit[pos++] = x%10; x /= 10; } return dfs(pos-1,-1,true,true,0,0); } int main() { // freopen("1.in.cpp","r",stdin); int t,ca=0; LL l,r; cin>>t; memset(dp,-1,sizeof(dp)); while(t--) { cin>>l>>r; printf("Case #%d: ",++ca); cout<<solve(r)-solve(l-1)<<endl; } return 0; }