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

· · 题解

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

读题

发现要输出 n 个情况下的最优解，最好肯定一次把所有情况都算完，考虑 dp。

状态

这道题用答案作为状态即可。用 f_i 表示结果为 i 的表达式的最小代价。

转移

题目明显给出了两种转移方式：

  1. 加法：f_i = \min _{1 \le j < i} (f_{i-j} + f_j + b)。
  2. 乘法：f_i = \min _{1 \le j < i} (f_{i/j} + f_j + c)，理论上来说，这样写不会有很大问题，但是为了逻辑严谨：
    • 我们把 j 的下界定为 2，不然会使用自己更新，这在逻辑上不合理。
    • 只在 i | j 时更新，因为非整数状态未定义（尽管 C++ 会自动帮你向下取整）。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 3e3+7,inf = LLONG_MAX;
int n,a,b,c,f[maxn];
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++)f[i] = inf;f[1] = a;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++)f[i] = min(f[i],f[i-j] + f[j] + b);
        for(int j=2;j<i;j++)if(i%j == 0)f[i] = min(f[i],f[i/j] + f[j] + c);
        cout<<f[i]<<' ';
    }
    return 0;
}