[SCOI2009] Windy数 - 数位dp

标签：个数   选择   正整数   ret   line   turn   cpp   bre   印象   

调数位，两行泪

好久没写数位dp了，这当然是因为队友zyf大佬dp实在太猛，orzorz

印象中唯一写过一次是在某一次区域赛的热身赛上（而且我还写翻车了）

所以今天的主题就是数位DP吧

不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。在A和B之间，包括A和B，总共有多少个windy数？

设 \(f[i][j]\) 从低到高 \(i\) 位，第\(i\)位是\(j\)的方案数

初态：\(f[1][i] = 1\)

转移：\(f[i][j]=f[i-1][k]\), 需要满足若干约束条件

如何统计答案？

对于位数比 \(n\) 小的，直接统计即可

对于位数相同的，枚举哪一位开始比 \(n\) 小，这样更高的位就确定了，更低的位只需要暴力选择即可

#include 
using namespace std;

int f[15][15];
const int m = 10;
int t[15];

int calc(int n) {
    if(n==0) return 0;
    int ans = 0;
    int x = n, y = 0;
    while(x) {
        t[++y] = x % 10;
        x /= 10;
    }
    int len = y;
    for(int i=1;i=0;--i) {
        if(i==0) {++ans; break;}
        if(i=2)) {
                if(i==1) ++ans;
                else for(int k=0;k=2) {
                        ans += f[i-1][k];
                    }
                }
            }
        }
    }
    return ans;
}

int main() {
    for(int i=0;i=2) {
                    f[i][j] += f[i-1][k];
                }
            }
        }
    }
    int a,b;
    cin>>a>>b;
    cout

[SCOI2009] Windy数 - 数位dp

标签：个数   选择   正整数   ret   line   turn   cpp   bre   印象   

原文地址：https://www.cnblogs.com/mollnn/p/12259558.html