luogu P2657 [SCOI2009]windy数数位dp 记忆化搜索

2021-07-11 14:07

阅读：381

标签：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

上一篇：C#中字符串的截取

下一篇：【原创】C# API 未能创建 SSL/TLS 安全通道问题解决

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：luogu P2657 [SCOI2009]windy数数位dp 记忆化搜索
文章链接：http://soscw.com/essay/103742.html

亲，登录后才可以留言！

luogu P2657 [SCOI2009]windy数数位dp 记忆化搜索

题目链接

题解

代码

评论

热门文章

推荐文章

最新文章

置顶文章

luogu P2657 [SCOI2009]windy数 数位dp 记忆化搜索

题目链接

题解

代码

评论

热门文章

推荐文章

最新文章

置顶文章

luogu P2657 [SCOI2009]windy数数位dp 记忆化搜索