数位DP之奥义

恩是的没错数位DP的奥义就是一个简练的dfs模板

 int dfs(int position, int condition, bool boundary) {
if (position < ) return (condition ?);
if (condition < ) return ;
if (!boundary && ~f[position][condition]) return f[position][condition];
int respond = ;
int top = boundary ? num[position] : ;
for (int i = ; i <= top; ++i)
respond += dfs(position - , new_s(condition, i), boundary && i == top);
return boundary ? respond : f[position][condition] = respond;
}

f是记忆化数组 其他看变量名就知道意思了吧

核心在于return里condition的条件以及new_s(condition, i)的构造方式

i从0还是1开始计数还要考虑题目里的前缀0条件

简化版

int dfs(int pos, int con, bool e) {
if (pos < ) return (con ?);
if (con < ) return ;
if (!e && ~f[pos][con]) return f[pos][con];
int res = ;
int top = e ? num[pos] : ;
for (int i = ; i <= top; ++i)
res += dfs(pos - , new_s(con, i), e && i == top);
return e ? res : f[pos][con] = res;
}

以及血的教训 多数情况dfs出来的f的数据是通用的 不用每次输入都memset掉

会TLE!!!

参考资料:http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html

上一篇:数位DP


下一篇:292. Nim Game