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

hlb44 · 2025-12-02 22:21:41 · 题解

容易发现每个数可通过加法或乘法拆分为更小的数，可以通过 dp 记录最小代价。

状态定义：设 dp_i 为构造结果为 i 的表达式的最小代价。

初始化：dp_1 = a，其余为无穷大 10^{18}。

状态转移：对于每个 i \geq 2，通过两种拆分方式更新 dp_i：

加法拆分：将 i 拆分为 j + (i-j)（j \in [1,i-1]），代价为 dp_j + dp_{i-j} + b，即 dp_i = \min(dp_i, dp_j + dp_{i-j} + b)。

乘法拆分：将 i 拆分为 j \times k（具体参考代码），代价为 dp_j + dp_k + c，即 dp_i = \min(dp_i, dp_j + dp_k + c)。

复杂度：O(n^2)。

代码

#include <bits/stdc++.h>
#define fo(i,begin,end) for(int i=(begin);i<=(end);++i)
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll dp[3005];
int n,a,b,c;

inline void read(int &x) {
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}

inline void write(ll x) {
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int main() {
    read(n),read(a),read(b),read(c);
    fo(i,1,n) dp[i]=INF;
    dp[1]=a;
    fo(i,2,n) {
        // 加法拆分
        fo(j,1,i-1) dp[i]=min(dp[i],dp[j]+dp[i-j]+b);
        // 乘法拆分
        int sq=sqrt(i);
        fo(j,2,sq) {
            if(i%j==0) {
                int k=i/j;
                dp[i]=min(dp[i],dp[j]+dp[k]+c);
            }
        }
    }
    fo(i,1,n) {
        write(dp[i]);
        if(i<n) putchar(' ');
    }
    putchar('\n');
    return 0;
}