数位 DP
经典题型¶
数位 DP 问题往往都是这样的题型,给定一个闭区间
例题SCOI2009 windy 数
题目大意:给定一个区间
首先我们将问题转化成更加简单的形式。设
分开求解这两个问题。
对于一个小于
有了这个性质,我们可以定义
写出 状态转移方程 :
这里的
我们发现,尽管前缀所选择的状态不同,而
核心代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | int dfs(int x, int st, int op) // op=1 =;op=0 <
{
if (!x) return 1;
if (!op && ~f[x][st]) return f[x][st];
int maxx = op ? dim[x] : 9, ret = 0;
for (int i = 0; i <= maxx; i++) {
if (abs(st - i) < 2) continue;
if (st == 11 && i == 0)
ret += dfs(x - 1, 11, op & (i == maxx));
else
ret += dfs(x - 1, i, op & (i == maxx));
}
if (!op) f[x][st] = ret;
return ret;
}
int solve(int x) {
memset(f, -1, sizeof f);
dim.clear();
dim.push_back(-1);
int t = x;
while (x) {
dim.push_back(x % 10);
x /= 10;
}
return dfs(dim.size() - 1, 11, 1);
}
|
几道练习题¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用