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

syh110213 · 2025-12-02 17:39:45 · 题解

思路

考虑 DP。

显然，f_1 = a。

对于 f_i，有两种转移方法：

加法：f_i = f_j + f_{j - i} + b，其中 j \in [1,i)。
乘法：f_i = f_j + f_k + c，其中 j \ge 2,k \ge 2 且 j \times k = i。

所以状态转移方程为：

f_i = \min \left( \min_{1 \le j < i} f_j + f_{j-i} +b,\min_{j,k \ge 2,j \times k = i} f_j + f_k + c \right)

时间复杂度：O(n^2)。

:::success[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,c,dp[3005];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> a >> b >> c;
    memset(dp,0x3f,sizeof dp);
    dp[1]=a;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;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;
}

:::