题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3886
题意：这题的题意有点晦涩难懂，大概意思就是给你一个区间，让你找一些满足递增递减条件的数，举个列：/-，要匹配这个关系，把一个数字分成一列数位，满足先递增，然后相等，然后递减的关系：ie:123321，1221，123441，这些都满足/-。
题解：设dp[i][j][k]表示考虑到第i位，上一个数为j，匹配关系到了k，然后DP下去就行了，注意处理左区间-1和前导零
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #define F(i,a,b) for(int i=a;i<=b;i++) 5 typedef long long LL; 6 char ops[111],a[111],b[111]; 7 int dig[111],st,len,oplen; 8 LL N=(LL)1e10,dp[111][11][111]; 9 10 int check(int pre,int now,int idx){ 11 char c=ops[idx]; 12 if(c=='/')return pre<now; 13 else if(c=='-')return pre==now; 14 return pre>now; 15 } 16 LL dfs(int pos,int idx=0,int pre=0,int z=0,bool inf=1){ 17 if(!pos)return idx==oplen; 18 if(!inf&&~dp[pos][pre][idx])return dp[pos][pre][idx]; 19 int end=inf?dig[pos]:9;LL ans=0; 20 F(i,0,end){ 21 if(!z)ans+=dfs(pos-1,idx,i,z||i,inf&&i==end),ans%=N; 22 else if(idx<oplen&&check(pre,i,idx)) 23 ans+=dfs(pos-1,idx+1,i,z||i,inf&&i==end),ans%=N; 24 else if(idx>0&&check(pre,i,idx-1)) 25 ans+=dfs(pos-1,idx,i,z||i,inf&&i==end),ans%=N; 26 } 27 if(!inf)dp[pos][pre][idx]=ans; 28 return ans; 29 } 30 31 void f_ck(){ 32 memset(dp,-1,sizeof(dp)); 33 oplen=strlen(ops); 34 for(st=0,len=0;a[st]=='0';)st++; 35 int end=strlen(a); 36 for(int i=end-1;i>=st;i--)dig[++len]=a[i]-'0'; 37 dig[1]--;//处理左区间-1 38 for(int i=1;dig[i]<0;)dig[i]=9,dig[i+1]--; 39 LL tmp=(len==0)?0:dfs(len); 40 for(st=0,len=0;b[st]=='0';)st++; 41 end=strlen(b); 42 for(int i=end-1;i>=st;i--)dig[++len]=b[i]-'0'; 43 LL an=dfs(len)-tmp+N; 44 printf("%08lld ",an%(LL)1e8); 45 } 46 47 int main(){ 48 while(~scanf("%s%s%s",ops,a,b))f_ck(); 49 return 0; 50 }