hdu 3886 Final Kichiku “Lanlanshu” (数位dp) - c++编程基础

TOP

hdu 3886 Final Kichiku “Lanlanshu” (数位dp)

2015-07-20 17:47:34 来源: 作者: 【大中小】浏览:2次

Tags：hdu 3886 Final Kichiku Lanlanshu (数位

给出一个字符，只含'/'，'-' ，'' ，表示着一个数上的各位数字按相应字符上升，不变或下降，问【a,b】区间内这样的数有多少个？

数组很好设，dp[i][j][k]表示处理到第i位，它对应的字符是第j位，它前面的数字是k的种类数。

令我纠结好久的是，我起初设的dp[i][j][k]表示处理到第i位时，它的上一位对应的字符是第j位，它的上一位数字是k的种类数，这样可能会导致一个'/'只有一个数字，但是题目要求是'/'’-‘''必须是至少两个相邻的数字满足。

如果把j理解为当前第i位应该对应的是第j个字符，那么只需拿当前取的数字num和k相比是否满足s[j]这种关系，若满足，就继续递归下一个字符，若不满足，就拿num和k相比是否满足s[j-1]关系，如果满足，就继续递归s[j]这种关系。

从这题可以得出结论，设置状态的时候，要针对当前这一位，尽量让当前这一位的选择是确定的。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#define LL __int64 #define LL long long #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; const int mod = 1e8; char s[110],a[110],b[110],dig[110]; int slen,alen; int dp[110][110][12]; bool check(int a, int b, char ch) { if(ch == '/') return a < b; else if(ch == '-') return a == b; else return a > b; } int dfs(int len, int pos, int pre, int up, int first) { if(len == alen) { return pos==slen; } if( !up && !first && dp[len][pos][pre] != -1 ) return dp[len][pos][pre]; int n = up ? (dig[len]-'0') : 9; int res = 0; for(int i = 0; i <= n; i++) { if(first) res += dfs(len+1,0,i,up&&i==n,first&&i==0); else { if( pos < slen && check(pre,i,s[pos]) ) res += dfs(len+1,pos+1,i,up&&i==n,0); else if(pos > 0 && check(pre,i,s[pos-1]) ) res += dfs(len+1,pos,i,up&&i==n,0); } res %= mod; } if(!up && !first) dp[len][pos][pre] = res; return res; } int cal(char x[], int f) { memset(dp,-1,sizeof(dp)); alen = strlen(x); int st = 0; while(x[st] == '0') st++; if(st >= alen) return 0; if(f == 1) //处理a-1 { for(int i = alen-1; i >= st; i--) { if(x[i] >= '1') { x[i]--; break; } else { x[i] = '9'; } } } strcpy(dig,x); return dfs(st,0,0,1,1); } int main() { while(~scanf(%s,s)) { slen = strlen(s); scanf(%s %s,a,b); printf(%08d ,((cal(b,0) - cal(a,1)%mod)+mod)%mod ); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVa1635 - Irrelevant Elements（..	下一篇：UVA 11294 POJ 3648 Wedding

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: