luogu P2657 [SCOI2009]windy数 数位dp 记忆化搜索
2021-07-11 14:07
阅读：501
标签：href 记忆化搜索 etc code ref ble 记忆话搜索 amp 题目
题目链接
luogu P2657 [SCOI2009]windy数
题解
我有了一种所有数位dp都能用记忆话搜索水的错觉
代码
#include
#include
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c '9') c = getchar();
while(c = '0') x = x * 10 + c - '0',c = getchar();
return x * f ;
}
int a,b;
int f[100][100];
int num[100];
int tot;
int dfs(int n,int lim,int pre) {
if(n == 0) return 1;
if(!lim && f[n][pre]) return f[n][pre];
int sum = 0;
for(int i = 0;i = 2) sum += dfs(n - 1,lim && i == num[n],i);
}
if(!lim) f[n][pre] = sum ;
return sum;
}
int solve(int x) {
int tot = 0;
while(x) num[++ tot] = x % 10,x /= 10;
return dfs(tot,1,-1);
}
int main() {
a = read(),b = read();
printf("%d\n", solve(b) - solve(a - 1));
return 0;
} luogu P2657 [SCOI2009]windy数 数位dp 记忆化搜索
标签：href 记忆化搜索 etc code ref ble 记忆话搜索 amp 题目
原文地址：https://www.cnblogs.com/sssy/p/9637193.html
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：luogu P2657 [SCOI2009]windy数 数位dp 记忆化搜索
文章链接：http://soscw.com/index.php/essay/103742.html
文章标题：luogu P2657 [SCOI2009]windy数 数位dp 记忆化搜索
文章链接：http://soscw.com/index.php/essay/103742.html
评论
亲，登录后才可以留言！