数位DP小记 + HDU 2089 不要62

本文主要是介绍数位DP小记 + HDU 2089 不要62，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【背景】

【思路】

采用记忆化搜索实现。

搜索：dfs(i,j,k,ismax)

这题的P(i)是不含有4和62的数，那么只需dfs(i,is6,ismax)即可，表示当前搜索到第i位，前一位是否为6(因为要判断后面那个是否为2)，是否达到上限。记忆dp[i][ismax]，搜索入口为dfs(len,false,true)

完整代码：

/*15ms,232KB*/#include<cstdio>
#include<cstring>
const int mx = 10;int bit[mx], dp[mx][2];///复杂度O(log n)
///若ismax为true则后面循环的时候i只能取0~bit[len]
///is6记录上一位是否为6
int dfs(int len, bool is6, bool ismax)
{if (len == 0) return 1; ///能递归到这里说明这串数符合要求，返回1if (!ismax && dp[len][is6] >= 0) return dp[len][is6];///若ismax为true，则还需要继续向下递归///为什么?对于n=5321来说，递归中的2xxx和3xxx可以直接在len=3时返回(因为xxx这颗子树已经被前面的1xxx算出来了)///但是在算5xxx时并不能直接返回，因为后面的xxx至多能取到321，还需要进一步往下递归int cnt = 0, maxnum = (ismax ? bit[len] : 9);for (int i = 0; i <= maxnum; ++i){if (i == 4 || is6 && i == 2) continue; ///不能有4，或者前一位为6且该位为2cnt += dfs(len - 1, i == 6, ismax && i == maxnum); ///ismax && i == maxnum 用来判断是否达到位值上限}return ismax ? cnt : dp[len][is6] = cnt; ///根据ismax来决定是否记录dp(比如dp[3][1]记录的是6xx的所有数，即从600到699中的符合条件的数的个数)
}int f(int n)
{int len = 0;while (n){bit[++len] = n % 10;n /= 10;}return dfs(len, false, true); ///从首位开始递归统计
}int main()
{int a, b;memset(dp, -1, sizeof(dp));while (scanf("%d%d", &a, &b), a)printf("%d\n", f(b) - f(a - 1));return 0;
}

转载请注明：http://blog.csdn.net/synapse7/article/details/21006265

这篇关于数位DP小记 + HDU 2089 不要62的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---