给你一个字符串/表示当前位比前一位小-表示和前一位相等\ 表示比前一位大  求a到b之间有多少个数满足方案

dp[i][j][k] 到第i位满足字符串的第j位前一位是k的方案数

#include <cstdio>#include <cstring>using namespace std;const int maxn = 110;char s[maxn], A[maxn], B[maxn];int a[maxn];int dp[maxn][maxn][10];int m;bool ok(int i, int j, char c){     if(c == '/') return i < j;     if(c == '-') return i == j;     if(c == '\\') return i > j;}int dfs(int x, int l, int p, int first, int flag){	if(x == -1)		return l == m;	if(!flag && dp[x][l][p] != -1)		return dp[x][l][p];	int end;	if(flag)		end = a[x];	else		end = 9;	int ans = 0;	for(int i = 0; i <= end; i++)	{		if(first)		{			ans += dfs(x-1, l, i, first&&i==0, flag&&i == end);			ans %= 100000000;		}		else if(l < m && ok(p, i, s[l]))		{			ans += dfs(x-1, l+1, i, first&&i==0, flag&&i == end);			ans %= 100000000;		}		else if(l > 0 && ok(p, i, s[l-1]))		{			ans += dfs(x-1, l, i, first&&i==0, flag&&i == end);			ans %= 100000000;		}	}	if(!flag)		dp[x][l][p] = ans;	return ans;}int cal(char* s, int flag){	int len = 0, n = strlen(s);	int j = 0;	while(s[j] == '0')		j++;	for(int i = n-1; i >= j; i--)		a[len++] = s[i] - '0';	if(flag)	{		for(int i = 0; i < len; i++)		{			if(a[i])			{					a[i]--;				break;			}			else				a[i] = 9;		}	}	return dfs(len-1, 0, 0, 1, 1);}int main(){	while(scanf("%s", s) != EOF)	{		memset(dp, -1, sizeof(dp));		m = strlen(s);		scanf("%s %s", A, B);		printf("%08d\n", (cal(B, 0)-cal(A, 1)+100000000)%100000000);	}	return 0;} 

HDU 3886 Final Kichiku “Lanlanshu” 数位DP