题解：P14644 [POI 2025/2026 #1] 表达式 / Arithmetic expression

rimu_awa · 2025-12-02 17:19:57 · 题解

思路

首先很容易想到，我们可以把每个表达式的代价表达为 A_i \times a + B_i \times b + C_i \times c，其中，A_i,B_i,C_i 分别是使用这几个代价的次数。（样例解释也给了我们提示）

我们可以得到一个性质：一个数可以由另两个比它小的数相加得到，也可以由另两个比它小的数相乘得到，而且我们不关心这两个数的代价是怎么来的，也就是说，我们只需要能算我们当前的这个数的代价就好了。

所以我们可以一个数一个数考虑。

假设我们现在想要计算表达式求值为 n 的代价。

观察题目，发现题目中只有两种操作：

• X + Y

  此时：

  A_n=A_X+A_Y\\B_n=B_X+B_Y+1\\C_n=C_X+C_Y

  可以理解为我多使用了一个加号，需要多付出 b 的代价。

• X \times Y

  此时：

  A_n=A_X+A_Y\\B_n=B_X+B_Y\\C_n=C_X+C_Y+1

  可以理解为我多使用了一个乘号，需要多付出 c 的代价。

很显然，这就是一个记忆化搜索（也可以说是动态规划）。于是我们只要枚举每个数转移。初始的时候假设我们用若干个 1 相加得到当前数，也就是说，初始代价是：

代码

记得开long long，没开吃了一发 WA :(

#include <bits/stdc++.h>
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << x << "\n"
#define pii pair<int, int>
#define pb push_back
#define int long long
using namespace std;
int n, a[3007], b[3007], c[3007], ans[3007], A, B, C;
void dp(int x){
    // plus
    for(int i = 1;i <= x / 2;i++){
        if((a[i] + a[x - i]) * A + (b[i] + b[x - i] + 1) * B + (c[i] + c[x - i]) * C < ans[x]){
            a[x] = a[i] + a[x - i];
            b[x] = b[i] + b[x - i] + 1;
            c[x] = c[i] + c[x - i];
            ans[x] = a[x] * A + b[x] * B + c[x] * C;
        }
    }
    // times
    for(int i = 2;i * i <= x;i++){
        if(x % i) continue;
        if((a[i] + a[x / i]) * A + (b[i] + b[x / i]) * B + (c[i] + c[x / i] + 1) * C < ans[x]){
            a[x] = a[i] + a[x / i];
            b[x] = b[i] + b[x / i];
            c[x] = c[i] + c[x / i] + 1;
            ans[x] = a[x] * A + b[x] * B + c[x] * C;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> A >> B >> C;
    for(int i = 1;i <= n;i++){
        ans[i] = A * i + B * (i - 1);
        a[i] = i;
        b[i] = i - 1;
        dp(i);
    }
    for(int i = 1;i <= n;i++) cout << ans[i] << " ";
}