数位DP

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int dp[20][2][2];
// dp[pos][last1][limit]
// pos   = 当前处理第几位
// last1 = 上一位是否是1（0或1）
// limit = 是否贴着上界（0或1）
// 值 = 从该状态开始的合法方案数

string s;  // 把数字 n 转成字符串形式

// DFS：从第 pos 位开始，统计合法方案数
// last1 = 上一位是否是1
// limit = 前面的位是否都贴着上界
int dfs(int pos, int last1, int limit) {
    // 递归终止：所有位都处理完了，找到了一个合法数
    if (pos == (int)s.size()) return 1;

    // 记忆化：如果 limit==0，可以直接用缓存的结果
    // limit==1 时不能缓存，因为每种上限情况不同
    if (!limit && dp[pos][last1][0] != -1)
        return dp[pos][last1][0];

    // 当前位能放的最大数字
    // 如果 limit==1，最多放 s[pos]（n的对应位）
    // 如果 limit==0，可以放 0-9（十进制）或 0-1（二进制）
    int up = limit ? s[pos] - '0' : 9;  // 改成1就是二进制版本

    int res = 0;  // 方案数累计

    // 枚举当前位放什么数字 d
    for (int d = 0; d <= up; d++) {
        // 本题限制：不能连续出现两个1
        if (last1 && d == 1) continue;  // 上一位是1且当前位也是1，跳过

        // 递归处理下一位
        // 新的 last1 = (当前位d是否为1)
        // 新的 limit = (之前的limit为1 且 当前位d等于上界up)
        res += dfs(pos + 1, d == 1, limit && (d == up));
    }

    // 记忆化：只在非限制时缓存
    if (!limit) dp[pos][last1][0] = res;
    return res;
}

// 求 [1, n] 中满足条件的数的个数
int solve(int n) {
    s = to_string(n);       // 把 n 转成字符串
    memset(dp, -1, sizeof(dp));  // -1 表示未计算
    return dfs(0, 0, 1);    // 从第0位开始，上一位不是1，贴着上界
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}