AT_abc403_f [ABC403F] Shortest One Formula

AT_abc403_f [ABC403F] Shortest One Formula

洛谷题目传送门

atcoder题目传送门

题目描述

给定一个正整数 $N$。

请找出由字符 1、+、*、(、) 组成的数学表达式中，满足以下所有条件的最短表达式 $S$：

1. $S$ 符合以下 BNF 语法 中 <expr> 符号的定义
2. $S$ 表示的数学表达式计算结果等于 $N$

BNF 语法定义如下：

<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number> 

符合 <expr> 定义的表达式示例：

• 1111+111：表示 $1111+111$
• (1+1)*(1+1)：表示 $(1+1)\times (1+1)$
• (11+(1+1)*(1+1))+1：表示 $(11+(1+1)\times (1+1))+1$

不符合 <expr> 定义的表达式示例：

• (1+1)(1+1)
• 1+2
• 1-1
• 1/1
• )1(
• 1++1
• +1
• (+1)
• 1*+1

输入格式

输入通过标准输入给出，格式如下：

$N$

输出格式

输出满足条件的最短表达式。

输入输出样例 #1

输入 #1

9

输出 #1

(1+1+1)*(1+1+1)

输入输出样例 #2

输入 #2

11

输出 #2

11

输入输出样例 #3

输入 #3

403

输出 #3

1+(1+1+1)*(1+11+11+111)

说明/提示

约束条件

• $1\le N\le 2000$
• 输入均为整数

样例解释 #1

值为 $9$ 的表达式可能有多种形式，例如：

• (1+1+1)*(1+1+1)
• 1+1+1+1+1+1+1+1+1
• (1+1)*(1+1)*(1+1)+1

其中 (1+1+1)*(1+1+1) 是最短的表达式。

思路详解

题目分析

根据题意，所谓的符合 <expr> 定义的表达式的式子其实有如下性质：

1. 数字部分只由1组成。
2. 运算只有+，*，()。

由于他要求结果为$N$的最短表达式，我们可以先考虑求出最短表达式的长度。在这里我们可以考虑$dp$。可以考虑如下的$dp$：

$dp$思路1

1. $dp$定义：设$f_i$为表达式的结果为$i$的最短表达式长度，但是只靠这一个我们就可以更新吗？看似没有问题，不过我们发现在进行乘法运算时会有问题，此时$f_i$可能会是形如$A+B$的形式，此时不能进行乘法。那我们考虑再定义$g_i$为表达式结果为$i$，且可以进行乘法转移(形如$A\ast B$或$(A)$)的最短字符串长度。
2. 状态转移：显然$1,11,111,1111$这4个数字可以直接判断。首先考虑加法，加法只能是$f_i$转移，所以可得$f_i=min(f_j+f_{i-j}+1)$。此时我们可以在$f_i$外套一个括号，所以得$g_i=f_i+2$。再考虑乘法，乘法$g_i,f_i$都可以转移，所以得$f_i=g_i=min(g_{i/j}+g_j+1)$。
3. 答案：最短字符串长度显然为$f_N$。

求解字符串

思考我们如何求解字符串，既然我们都使用$dp$了，那我们可以在$dp$过程中记录一下$f_i$和$g_i$由何转移而来。

$dp$思路2

1. $dp$定义：定义$pre{f}_i$与$pre{g}_i$分别表示$f_i$与$g_i$从何转移而来。
2. 状态转移：若数字为$1,11,111,1111$，则$pre{f}_i=pre{g}_i=0$。在加法转移中，$pre{f}_i=j$，表示他由$j+(i-j)$转移。套括号时，记录$pre{g}_i=i$，表示他是由$f_i$套括号形成的。在乘法中，记录$pre{g}_i=j,pre{f}_i=-j$表示他们是由$j+(i/j)$转移得到。
3. 答案：最后递归输出即可

code

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n;
int f[N],g[N];
int pref[N],preg[N];
void find(int i,int k){//递归求出答案，k==0代表为f，否则为gif(k==0){if(pref[i]==0){cout<<i;}//直接输出，i=1,11,111,1111else if(pref[i]>0){find(pref[i],0);cout<<'+';find(i-pref[i],0);}//pref[i]>0表示为加法运算else {find(-pref[i],1);cout<<'*';find(i/(-pref[i]),1);}//否则为乘法运算，记得要变为g}else{if(preg[i]==0){cout<<i;}//直接输出else if(preg[i]==i){cout<<'(';find(i,0);cout<<')';}//套括号输出felse {find(preg[i],1);cout<<'*';find(i/(preg[i]),1);}//乘法运算，注意还是g}
}
int main(){cin>>n;memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));for(int i=1;i<=n;i++){if(i==1){f[i]=g[i]=1;pref[i]=preg[i]=0;}else if(i==11){f[i]=g[i]=2;pref[i]=preg[i]=0;}else if(i==111){f[i]=g[i]=3;pref[i]=preg[i]=0;}else if(i==1111){f[i]=g[i]=4;pref[i]=preg[i]=0;}else{for(int j=1;j<i;j++)if(f[j]+f[i-j]+1<f[i])f[i]=f[j]+f[i-j]+1,pref[i]=j;//加法g[i]=f[i]+2;preg[i]=i;//f外套括号for(int j=2;j<i;j++)if(i%j==0&&g[i/j]+g[j]+1<g[i])g[i]=g[i/j]+g[j]+1,preg[i]=j;//乘法if(g[i]<f[i])f[i]=g[i],pref[i]=-preg[i];//f也可能为乘法}}find(n,0);return 0;
}