题解：AT_abc403_f [ABC403F] Shortest One Formula

cheng2010 · 2025-04-28 13:05:07 · 题解

打题时被自己唐死了。

首先拿到题感觉似乎不太可做，但看到 n \le 2000 果断暴搜。

首先肯定要记忆化。

我们定义 f(x) 为组成 x 的最短字符串，在搜索中先找加再找积，然后取 \min，于是很容易可以写出代码：

bz[1]="1";
bz[11]="11";
bz[111]="111";
bz[1111]="1111";

string dfs(int x)
{
    if(bz[x]!="\0") return bz[x];
    if(f[x]!="\0") return f[x];
    string res="\0";
    for(int i=1;i<x;i++) res=cmp(res,dfs(i)+'+'+dfs(x-i));
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
            res=cmp(res,'('+dfs(i)+')'+'*'+'('+dfs(x/i)+')');
    return f[x]=res;
}

然后就发现 WA 了。

想想为什么？

我们发现有一个 bug 就是在乘的时候我们加了两个括号！这就导致加了两个括号后长度加了 2 使得答案变劣。

比如：

987=11+(1+1)*(1+1+1+1)*(11+111)=11+(1+1+1+1)*(11+11+111+111)

它们的区别就是对 244 的分解。

244=(1+1)*(11+111)=11+11+111+111

对 244 而言，显然后者更优，但对于 987 就是前者，这就是括号的问题。

那该怎么办？我们只用加一维：f(x,pos) 表示外层是否有括号，这样在加时添上括号即可，于是有了最终代码：

inline string dfs(int x,bool pos)
{
    if(bz[x]!="\0") return bz[x];
    if(f[x][pos]!="\0") return f[x][pos];
    string res="\0";
    if(pos)
    {
        for(int i=1;i<x;i++) res=cmp(res,'('+dfs(i,0)+'+'+dfs(x-i,0)+')');
    }
    else
    {
        for(int i=1;i<x;i++) res=cmp(res,dfs(i,0)+'+'+dfs(x-i,0));
    }
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
            res=cmp(res,dfs(i,1)+'*'+dfs(x/i,1));
    return f[x][pos]=res;
}

时间应该是 O(n^2) 的。