我的同学出了一道很有趣的题目,一起来看看:

假设有一个数列 ${a_n}$:

$$
a_n =
\begin{cases}
1, & \text{当 } n \equiv 1 \pmod{3} \
4, & \text{当 } n \equiv 2 \pmod{3} \
4, & \text{当 } n \equiv 0 \pmod{3}
\end{cases}
$$ 其长度为 $3k$,其中每个元素按顺序排在一起.你需要通过加,减,乘,除四则运算将这些元素连接在一起,并且可以使用括号调整运算优先级,最终得到结果为 $1635$.顺序必须保持原数列中的顺序,即不能重新排列元素.求出最小的 $k$ ,使得通过这些操作能够得到结果 $1635$.

计算机真是快呢! 不到 1 秒就可以出结果了.

我们现在来思考这个问题. 这道题目有些像小时候做过的"24 点问题", 通过加减乘除凑出一个表达式,使其结果为 $24$ . 但不同的是这道题目里数更多, 并且支持括号. 这道题本质上就是给定一个特定的数组,将其分为左,右两半部分,再用加减乘除之一把它们合起来. 因此表达式可以为: 左区间的表达式 op 右区间的表达式 (op为运算符) 很自然地, 我们想到 区间 DP.

定义 $dp[l][r]$ 表示用第 $l$ 个到第 $r$ 个数,保持原顺序,任意加括号,插入四则运算以后,所有能得到的结果.
由于一个区间可能得到很多不同结果,所以 $dp[l][r]$不是单个数,而是一个哈希表.这个哈希表的键为一个分数, 其值为得到这个分数的表达式的string

只看前三个数 $1,4,4$.

长度为 1 时:

$$
\begin{aligned}
dp[1][1] &= {1} \
dp[2][2] &= {4} \
dp[3][3] &= {4}
\end{aligned}
$$

长度为 2 时:

$dp[1][2]$ 由 $1$ 和 $4$ 合并得到:

$$ \begin{aligned} 1+4 &= 5 \ 1-4 &= -3 \ 1\times4 &= 4 \ 1\div4 &= \frac{1}{4} \end{aligned} $$

所以 $dp[1][2]={5,-3,4,\frac{1}{4}}$

同理 $dp[2][3]$ 由 $4$ 和 $4$ 得到:

${8,0,16,1}$

长度为 3 时,要算 $dp[1][3]$.

枚举断点: 第一种切法是 $dp[1][1]$ 和 $dp[2][3]$
也就是拿 $dp[1][1]$ 里的$1$,和 $dp[2][3]$ 里的 ${8,0,16,1}$ 逐个配对做四则运算 第二种切法是 $dp[1][2]$ 和 $dp[3][3]$
也就是拿 $dp[1][2]$ 里的 ${5,-3,4,\frac{1}{4}}$,和 $dp[3][3]$ 里的 $4$去配对 之后,再类似地推到 $dp[1][3k]$, 这样我们就可以知道在 $r=3k$ 下能算出多少种数, 再从中查找$1635$, 若没有,则使$k++$并再算一次, 若有则输出结果为$1635$的表达式.因此,想要解决这个问题,自小到大地枚举 $k \in \mathbb{N}^+$ , 使得 $k$ 能满足题目条件, 即$dp[1][3k]$中有一个表达式的值为$1635$.

(代码中的变量名不全都和上文中的对应,见谅)

#include <iostream>  
#include <unordered_map>  
#include <string>  
#include <cstdlib>  
#define ll long long  
#define N 44 // shenmizhe  
#define TARGET 1635  
using namespace std;  

ll gcdll(ll a, ll b) {  
    while (b) {  
        ll t = a % b;  
        a = b;  
        b = t;  
    }  
    return a;  
}  

struct Frac {  
    ll p, q;  
    Frac(ll _p = 0, ll _q = 1) {  
        if (_q < 0) _p = -_p, _q = -_q;  
        if (_p == 0) {  
            p = 0;  
            q = 1;  
        } else {  
            ll g = gcdll(llabs(_p), llabs(_q));  
            p = _p / g;  
            q = _q / g;  
        }  
    }  
    bool operator == (const Frac& b) const {  
        return p == b.p && q == b.q;  
    }  
};  

struct HashFrac {  
    size_t operator () (const Frac& x) const {  
        return (size_t)(x.p * 1000003LL + x.q);  
    }  
};  

Frac addf(Frac a, Frac b) {  
    return Frac(a.p * b.q + b.p * a.q, a.q * b.q);  
}  

Frac subf(Frac a, Frac b) {  
    return Frac(a.p * b.q - b.p * a.q, a.q * b.q);  
}  

Frac mulf(Frac a, Frac b) {  
    return Frac(a.p * b.p, a.q * b.q);  
}  

bool divf(Frac a, Frac b, Frac& c) { // 分母不得为 0, 否则会发生除以 0 的错误  
    if (b.p == 0) return false;  
    c = Frac(a.p * b.q, a.q * b.p);  
    return true;  
}  

int a[N], m;  
Frac tgt(TARGET, 1); // 目标分数  

unordered_map<Frac, string, HashFrac> dp[N][N];  

void ins(unordered_map<Frac, string, HashFrac>& mp, Frac v, string s) {  
    if (!mp.count(v)) mp[v] = s; // 不在哈希表内就加入哈希表  
}  

bool solve(int n) {  
    m = 3 * n;  
    for (int i = 1; i <= n; i++) { // init  
        a[i * 3 - 2] = 1;  
        a[i * 3 - 1] = 4;  
        a[i * 3] = 4;  
    }  

    for (int i = 1; i <= m; i++) {  
        for (int j = i; j <= m; j++) {  
            dp[i][j].clear();  
        }  
    }  

    for (int i = 1; i <= m; i++) {  
        dp[i][i][Frac(a[i], 1)] = to_string(a[i]);  
    }  

    for (int len = 2; len <= m; len++) {  
        for (int l = 1; l + len - 1 <= m; l++) {  
            int r = l + len - 1;  
            for (int k = l; k < r; k++) {  
                // c++11  
                for (auto &L : dp[l][k]) {  
                    for (auto &R : dp[k + 1][r]) {  
                        ins(dp[l][r], addf(L.first, R.first), "(" + L.second + "+" + R.second + ")");  
                        ins(dp[l][r], subf(L.first, R.first), "(" + L.second + "-" + R.second + ")");  
                        ins(dp[l][r], mulf(L.first, R.first), "(" + L.second + "*" + R.second + ")");  
                        Frac v;  
                        if (divf(L.first, R.first, v)) {  
                            ins(dp[l][r], v, "(" + L.second + "/" + R.second + ")");  
                        }  
                    }  
                }  
            }  
        }  
    }  

    if (dp[1][m].count(tgt)) {  
        printf("Found min n=%d\n Expr %s",n,dp[1][m][tgt].c_str()); // 不喜欢用 cout  
        return true;  
    }  
    return false;  
}  

int main() {  
    for (int n = 1; n <= 8; n++) {  
        if (solve(n)) return 0;  
    }  
    printf("No solution\n");  
    return 0;  
}

但是经过测试发现这段代码运行得较慢 原来 对于每个区间$[l,r]$,都把这个区间所有可能结果完整求出来,这是全状态区间 DP, 于是我们可以对其进行修改, 对较小的区间进行预处理,而对于大区间我们采用定向 dfs,这样可以节约 999 时间. 此外还有一些修改,比如使用反推,以及string all_add(int l, int r),在代码中已经做了解释,相信读者能够看懂.

#include <iostream>  
#include <unordered_map>  
#include <string>  
#include <cstdlib>  
#define ll long long  
#define N 44 // shenmizhe  
#define TARGET 1635  
using namespace std;  

ll gcdll(ll a, ll b) {  
    while (b) {  
        ll t = a % b;  
        a = b;  
        b = t;  
    }  
    return a;  
}  

struct Frac {  
    ll p, q;  
    Frac(ll _p = 0, ll _q = 1) {  
        if (_q < 0) _p = -_p, _q = -_q;  
        if (_p == 0) {  
            p = 0;  
            q = 1;  
        } else {  
            ll g = gcdll(llabs(_p), llabs(_q));  
            p = _p / g;  
            q = _q / g;  
        }  
    }  
    bool operator == (const Frac& b) const {  
        return p == b.p && q == b.q;  
    }  
};  

struct HashFrac {  
    size_t operator () (const Frac& x) const {  
        return (size_t)(x.p * 1000003LL + x.q);  
    }  
};  

Frac addf(Frac a, Frac b) {  
    return Frac(a.p * b.q + b.p * a.q, a.q * b.q);  
}  

Frac subf(Frac a, Frac b) {  
    return Frac(a.p * b.q - b.p * a.q, a.q * b.q);  
}  

Frac mulf(Frac a, Frac b) {  
    return Frac(a.p * b.p, a.q * b.q);  
}  

bool divf(Frac a, Frac b, Frac& c) { // 分母不得为 0, 否则会发生除以 0 的错误  
    if (b.p == 0) return false;  
    c = Frac(a.p * b.q, a.q * b.p);  
    return true;  
}  

int a[N], m, K; // 只完整预处理长度 <= K 的区间  
Frac tgt(TARGET, 1); // 目标分数  

unordered_map<Frac, string, HashFrac> dp[N][N];  

void ins(unordered_map<Frac, string, HashFrac>& mp, Frac v, string s) {  
    if (!mp.count(v)) mp[v] = s; // 不在哈希表内就加入哈希表  
}  

struct Jiyi {  
    int l, r;  
    Frac t;  
    bool operator == (const Jiyi& b) const {  
        return l == b.l && r == b.r && t == b.t;  
    }  
};  

struct HashJiyi {  
    size_t operator () (const Jiyi& x) const {  
        size_t h = (size_t)x.l;  
        h = h * 1000003ULL + (size_t)x.r;  
        h = h * 1000003ULL + (size_t)(x.t.p * 1000003LL + x.t.q);  
        return h;  
    }  
};  

unordered_map<Jiyi, string, HashJiyi> jiyis;  

/*  
在某些特殊情况下,目标反推不是唯一的.  
0 * y = 0  
这时候 y 可以是很多东西,没法从 0 唯一反推出右边目标.  
因为题目里的数都是正数 1 和 4,就随便把剩下那段拼成一个合法表达式,例如一路加起来:  
(((1+4)+4)+1)...  
该表达式一定合法.  
*/  
string all_add(int l, int r) {  
    string s = to_string(a[l]);  
    for (int i = l + 1; i <= r; i++) {  
        s = "(" + s + "+" + to_string(a[i]) + ")";  
    }  
    return s;  
}  

string dfs(int l, int r, Frac T) {  
    Jiyi now = {l, r, T};  
    if (jiyis.count(now)) return jiyis[now];  

    int len = r - l + 1;  

    if (len <= K) {  
        if (dp[l][r].count(T)) return jiyis[now] = dp[l][r][T];  
        return jiyis[now] = "";  
    }  

    for (int k = l; k < r; k++) {  
        int lenL = k - l + 1;  
        int lenR = r - k;  

        // 总是枚举较短的那一边,减少状态数  
        if (lenL <= lenR) {  
            if (lenL > K) continue;  

            for (auto &L : dp[l][k]) {  
                Frac x = L.first, need;  
                string ex = L.second, ey;  

                // x + y = T biancheng y = T - x  
                need = subf(T, x);  
                ey = dfs(k + 1, r, need);  
                if (!ey.empty()) return jiyis[now] = "(" + ex + "+" + ey + ")";  

                need = subf(x, T);  
                ey = dfs(k + 1, r, need);  
                if (!ey.empty()) return jiyis[now] = "(" + ex + "-" + ey + ")";  

                if (x.p != 0) {  
                    if (divf(T, x, need)) {  
                        ey = dfs(k + 1, r, need);  
                        if (!ey.empty()) return jiyis[now] = "(" + ex + "*" + ey + ")";  
                    }  
                } else if (T.p == 0) {  
                    return jiyis[now] = "(" + ex + "*" + all_add(k + 1, r) + ")";  
                }  

                if (T.p != 0) {  
                    if (divf(x, T, need) && need.p != 0) {  
                        ey = dfs(k + 1, r, need);  
                        if (!ey.empty()) return jiyis[now] = "(" + ex + "/" + ey + ")";  
                    }  
                } else if (x.p == 0) {  
                    return jiyis[now] = "(" + ex + "/" + all_add(k + 1, r) + ")";  
                }  
            }  
        } else {  
            if (lenR > K) continue;  

            for (auto &R : dp[k + 1][r]) {  
                Frac y = R.first, need;  
                string ey = R.second, ex;  

                need = subf(T, y);  
                ex = dfs(l, k, need);  
                if (!ex.empty()) return jiyis[now] = "(" + ex + "+" + ey + ")";  

                need = addf(T, y);  
                ex = dfs(l, k, need);  
                if (!ex.empty()) return jiyis[now] = "(" + ex + "-" + ey + ")";  

                if (y.p != 0) {  
                    if (divf(T, y, need)) {  
                        ex = dfs(l, k, need);  
                        if (!ex.empty()) return jiyis[now] = "(" + ex + "*" + ey + ")";  
                    }  
                } else if (T.p == 0) {  
                    return jiyis[now] = "(" + all_add(l, k) + "*" + ey + ")";  
                }  

                if (y.p != 0) {  
                    need = mulf(T, y);  
                    ex = dfs(l, k, need);  
                    if (!ex.empty()) return jiyis[now] = "(" + ex + "/" + ey + ")";  
                }  
            }  
        }  
    }  

    return jiyis[now] = "";  
}  

bool solve(int n) {  
    m = 3 * n;  
    for (int i = 1; i <= n; i++) { // init  
        a[i * 3 - 2] = 1;  
        a[i * 3 - 1] = 4;  
        a[i * 3] = 4;  
    }  

    // 只完整预处理长度 <= K 的区间  
    K = m / 2;  
    jiyis.clear();  

    for (int i = 1; i <= m; i++) {  
        for (int j = i; j <= m; j++) {  
            dp[i][j].clear();  
        }  
    }  

    for (int i = 1; i <= m; i++) {  
        dp[i][i][Frac(a[i], 1)] = to_string(a[i]);  
    }  

    // 这里只做到 len <= K 而不是 m  
    for (int len = 2; len <= K; len++) {  
        for (int l = 1; l + len - 1 <= m; l++) {  
            int r = l + len - 1;  
            for (int k = l; k < r; k++) {  
                for (auto &L : dp[l][k]) {  
                    for (auto &R : dp[k + 1][r]) {  
                        ins(dp[l][r], addf(L.first, R.first), "(" + L.second + "+" + R.second + ")");  
                        ins(dp[l][r], subf(L.first, R.first), "(" + L.second + "-" + R.second + ")");  
                        ins(dp[l][r], mulf(L.first, R.first), "(" + L.second + "*" + R.second + ")");  
                        Frac v;  
                        if (divf(L.first, R.first, v)) {  
                            ins(dp[l][r], v, "(" + L.second + "/" + R.second + ")");  
                        }  
                    }  
                }  
            }  
        }  
    }  

    // 定向搜整个区间能否得到 tgt  
    string ans = dfs(1, m, tgt);  
    if (!ans.empty()) {  
        printf("Found min n=%d\nExpr %s\n", n, ans.c_str()); // 不喜欢用 cout  
        return true;  
    }  
    return false;  
}  

int main() {  
    for (int n = 1; n <= 8; n++) {  
        if (solve(n)) return 0;  
    }  
    printf("No solution\n");  
    return 0;  
}

(我电脑上还没装一些 c++编辑器 这里顺手用 pycharm 代替了) $$ {1+(4((4((1+4)((4+(1}{(4+4)))(1+4))))-4))}= 1635 $$ 完美!