P14644题解

_czy · 2025-12-03 13:53:42 · 题解

思路

发现 n 不是很大，考虑 DP。可以设 f_i 表示表达式求值结果为 i 时，表达式的最小代价。边界显然 f_1=a。

具体地说，对于 i，考虑最后一次是加还是乘。

如果是加则 f_i=\min f_j+f_{i-j}+b。

如果是乘则 f_i=\min f_j\times f_{\frac{i}{j}}+c。

然后直接记忆化搜索即可，当然你也可以打 DP。时间复杂度 O(n^2)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3003;
int n,a,b,c;
ll f[N];
ll dfs(int x){
    if(x==1)return a;
    if(f[x])return f[x];
    f[x]=1e18;
    for(int i=1;i<=x/2;i++)f[x]=min(f[x],dfs(i)+dfs(x-i)+b);
    for(int i=2;i*i<=x;i++)if(x%i==0)f[x]=min(f[x],dfs(i)+dfs(x/i)+c);
    return f[x];
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++)cout<<dfs(i)<<' ';
}