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

OvO_CYX · 2025-12-02 18:12:45 · 题解

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

题目传送门

题意简述

给定正整数 n,a,b,c，请你对于 1 \sim n 中的每一个 i，给出使值到 i 的最小代价。

其中，代价为 x,y，值为 p,q 的两个数可以通过加法得到一个代价为 x+y+b，值为 p+q 的式子，也可以通过乘法得到一个代价为 x+y+c，值为 p \times q 的式子。

思路

动态规划。 f_i 表示得到表达式的值为 i 的最小代价。那么很轻易地，我们就能写出两条状态转移方程：

• f_i=\min\{f_i,f_j+f_{i-j}+b\}$，其中 $j \in [1,i)

最后输出一行 n 个数，为答案。

::::warning[如果你有部分WA并拿下了13pts] 记得打开 long long ::::

::::info[code]

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

::::