HDU 3565 Bi-Peak Number：数位 DP 状态机求最大数位和

题目大意

峰值数：数位先增后减（位数≥3，首位非零）。Bi-Peak：两个峰值数拼接。求区间 [A,B] 内 Bi-Peak 数的最大数位和。

数位 DP 状态设计

dp[pos][pre][st]：当前处理第 pos 位（从高到低），前一位为 pre，状态 st，后缀能构成 Bi-Peak 的最大数位和。
7 种状态：

状态转移逻辑

int dfs(int pos, int pre, int st, bool f1, bool f2) {
    if (pos == -1) return st==6 ? 0 : -INF;
    if (f1 && f2 && dp[pos][pre][st]!=-1) return dp[pos][pre][st];
    int lo = f1 ? 0 : bit1[pos], hi = f2 ? 9 : bit2[pos];
    int ans = -INF;
    for (int d=lo; d<=hi; ++d) {
        int nst = -1;
        if (st==0 && d) nst=1;
        else if (st==1) { if (d>pre) nst=2; else nst=-1; }
        else if (st==2) { if (d==pre) nst=-1; else if (d>pre) nst=2; else nst=3; }
        else if (st==3) { if (dpre) nst=4; else nst=d?4:-1; }
        else if (st==4) { if (d>pre) nst=5; else nst=-1; }
        else if (st==5) { if (d>pre) nst=5; else if (dlo, f2||d

关键技巧

状态机建模：精确捕捉「先增后减」两次的结构
紧致上下界：f1/f2 标记是否已脱离 A/B 边界
记忆化：仅在无边界限制时备忘


复杂度

状态数：位数 ≤ 64 × 10 × 7 ≈ 4480
转移：每状态枚举 0~9
极快通过