题解：AT_abc403_f [ABC403F] Shortest One Formula

ZZ0520 · 2025-04-29 11:00:33 · 题解

题目大意

给定一个数 N，构造一个只包含 1，+，*，(，) 的合法算数表达式，使其结果恰好为 N，并使其长度最短，输出一种构造方案。

思路

• 用 dp[i] 表示数字 i 的最短字符串是什么，g[i] 表示数字 i 的字符串能否直接用于乘法（即不需要加括号）。

• 对于加法：dp[i]=dp[j]+'+'+dp[i-j]。

• 对于乘法：dp[i]=dp[j]+'*'+dp[i-j]。

• 注意：乘法的 dp[j] 和 dp[i-1] 前后需要根据情况加括号，是否加括号，可以取决于其之前是否是由乘法运算得来，如果是乘法运算得来，肯定可以直接用于乘法运算，所以我们需要辅助数组 g[i] 来表示数字 i 是否可以直接用于乘法运算。

• 固定的：当 N 为 1，11，111，1111 时，直接返回 N。

code

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int g[N];
/*
    dp[i] -> 数字i的字符串长什么样
    g[i] -> 数字i的字符串有没有括号
*/
int main(){
    int m=2009;
    vector<string> dp(m,string(2 * m,'!'));
    dp[1]="1"; 
    dp[11]="11"; 
    dp[111]="111"; 
    dp[1111]="1111";
    g[1]=g[11]=g[111]=g[1111]=1;
    for(int i=2;i<m;i++){
        if(i==11||i==111||i==1111){
            continue;
        }
        for(int j=1;i-j>=1;j++){
            if(dp[j].size()+dp[i-j].size()+1<dp[i].size()){
                dp[i]=dp[j]+"+"+dp[i-j];
            }
        }
        for (int j=2;j*j<=i;j++){
            if(i%j==0){
                if(dp[j].size()+dp[i/j].size()+1+2*!g[j]+2*!g[i/j]<=dp[i].size()){
                    string cur;
                    if(g[j]==0) cur+="(";
                    cur+=dp[j];
                    if(g[j]==0) cur+=")";
                    cur+="*";
                    if(g[i/j]==0) cur+="(";
                    cur+=dp[i/j];
                    if(g[i/j]==0) cur+=")";
                    dp[i]=cur;
                    g[i]=1;
                }
            }
        }
    }
    int n;
    cin>>n;
    cout<<dp[n]<<endl;
    return 0;
}