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

zhang__yi__cheng · 2025-12-03 12:37:51 · 题解

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

题目大意

给定 n,a,b,c，求构造值为 1\sim n 的表达式的最小代价：

基本思路

这道题用 动态规划 ：

1. 设 dp[i] 为值 i 的最小代价；
2. 初始化：dp[1]=a，i\ge2 初始为纯加法代价（i\cdot a + (i-1)\cdot b）；
3. 转移：
   • 加法：dp[i]=\min(dp[i], dp[j]+dp[i-j]+b)；
   • 乘法：dp[i]=\min(dp[i], dp[j]+dp[i/j]+c)。

AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a, b, c;
int main() {
    cin >> n >> a >> b >> c;
    vector<ll> dp(n + 1);
    dp[1] = a;
    for (int i = 2; i <= n; i++) {
        dp[i] = (ll)i * a + (i - 1) * b;
        for (int j = 1; j <= i / 2; j++) dp[i] = min(dp[i], dp[j] + dp[i - j] + b);
        for (int j = 2; j * j <= i; j++) if (i % j == 0) dp[i] = min(dp[i], dp[j] + dp[i / j] + c);
    }
    for (int i = 1; i <= n; i++) cout << dp[i] << " ";
    return 0;
}
}