题解：AT_abc403_f [ABC403F] Shortest One Formula

chenxi2009 · 2025-04-29 19:42:15 · 题解

思路

看到题解区代码都挺长的，我来发一发。

令 f_i 为表示 i 的最短字符串长度，g_i 为表示 i 的字符串中，最后一步运算不是加法（加了括号或只有一个数字也算）的最短字符串长度。

我们为每一种表达式中的符号设定转移方程：

• 1：f_1=g_1=1,f_{11}=g_{11}=2,f_{111}=g_{111}=3,f_{1111}=g_{1111}=4；
• +：f_i=\min\limits_{j=1}^{i-1} (f_j+f_{i-j}+1)
• *：f_i=g_i=\min\limits_{j\times k=i}(g_j+g_k+1)
• ()：g_i=\min(g_i,f_i+2)

然后我们就可以算出表示 N 的字符串的最短长度了。

但是我们还要找出一个对应的字符串 S，所以我们还要记录 ff_i 表示 f_i 是从哪里来的，gf_i 记录 g_i 是从哪里来的，输出的时候递归分类讨论。

具体分讨：

• 当前需要输出 f_x 对应的字符串：
• 输出 g_x 对应的字符串：

时间复杂度 O(N^2)，看转移式挺简单的不知道能不能做到 O(N\log N) 呢。

代码

#include<bits/stdc++.h>
using namespace std;
int n,f[3000],g[3000],ff[3000],gf[3000];
void output(int x,int kind){
    if(kind){//输出 g[x]
        if(!gf[x]) printf("%d",x);//由 1 组成
        else if(gf[x] == x) printf("("),output(x,0),printf(")");//f[x] 加上括号得到
        else output(gf[x],1),printf("*"),output(x / gf[x],1);//相乘得到
    }
    else{//输出 f[x]
        if(ff[x] == x) printf("%d",x);//由 1 组成
        else if(!ff[x]) output(x,1);//相乘得到
        else output(ff[x],0),printf("+"),output(x - ff[x],0);//相加得到
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++){
        if(i == 1) f[i] = g[i] = 1,ff[i] = 1,gf[i] = 0;
        else if(i == 11) f[i] = g[i] = 2,ff[i] = 11,gf[i] = 0;
        else if(i == 111) f[i] = g[i] = 3,ff[i] = 111,gf[i] = 0;
        else if(i == 1111) f[i] = g[i] = 4,ff[i] = 1111,gf[i] = 0;
        else{
            f[i] = 1e9;
            for(int j = 1;j < i;j ++) if(f[j] + f[i - j] + 1 < f[i]) f[i] = f[j] + f[i - j] + 1,ff[i] = j;//加法转移
            g[i] = f[i] + 2,gf[i] = i;//括号转移
            for(int j = 2;j < i;j ++) if(i % j == 0) if(g[j] + g[i / j] + 1 < g[i]) g[i] = g[j] + g[i / j] + 1,gf[i] = j;//乘法转移
            if(g[i] < f[i]) f[i] = g[i],ff[i] = 0;//f[x] 也有可能由乘法得到
        }
    }
    output(n,0);
    return 0;
}