题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3886
题意：给一定区间[A,B]，一串由/,\,-组成的符号串。求满足符号串的数字个数。
•/表示数字从左到右递增
•表示数字从左到右递减
•-表示数字从左到右相等
分析：dp[i][j][k]，表示当枚举到第i位的数，匹配str[j],前一位是k，满足要求的数字个数.
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define N 100010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; int dp[110][110][10]; int dig[110],len; char str[110],a[110],b[110]; int judge(int i,int pre,int now) { if(str[i]=='/')return pre<now; else if(str[i]=='-')return pre==now; else if(str[i]=='\')return pre>now; } int dfs(int pos,int cur,int pre,int limit,int fzore) { if(!pos)return cur==len; if(!limit&&~dp[pos][cur][pre])return dp[pos][cur][pre]; int ed=limit?dig[pos]:9; int ans=0; for(int i=0;i<=ed;i++) { if(!fzore) { if(cur<len&&judge(cur,pre,i)) ans+=dfs(pos-1,cur+1,i,limit&&i==ed,fzore&&!i); //这里为什么能往回走，因为如果pre,i满足str[cur-1]，同时 //已经知道“pre前一位，pre”也满足str[cur-1]，这样还是满足要求的数 //例如数据123455555554321是符合/-的，5之前都是/，中间都是-，后面都是。 else if(cur&&judge(cur-1,pre,i)) ans+=dfs(pos-1,cur,i,limit&&i==ed,fzore&&!i); } else ans+=dfs(pos-1,cur,i,limit&&i==ed,fzore&&!i); ans%=mod; } if(!limit)dp[pos][cur][pre]=ans; return ans; } int solve(char s[],bool left) { int lens=strlen(s),m=0,i=0; while(s[i]=='0'&&i<lens)i++; for(int j=lens-1;j>=i;j--)dig[++m]=s[j]-'0'; if(left&&m) { for(int i=1;i<=m;i++) { if(dig[i]) { dig[i]--;break; } else dig[i]=9; } } return dfs(m,0,0,1,1); } int main() { while(scanf("%s",str)!=EOF) { len=strlen(str); scanf("%s%s",a,b); memset(dp,-1,sizeof(dp)); printf("%08d ",((solve(b,0)-solve(a,1))+mod)%mod); } }