ABC-403-F - Shortest One Formula · znzryb
## 思路讲解
竟然每种表达式都能转移
::: 如果是推这个式子的长度，可以这么推
```cpp
// Problem: F - Shortest One Formula
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
ll N,M,K,T,A[MAXN];
// [0]是用加法拼出来的,[1]是用乘法拼出来的，或者不用加括号（这个属性会影响括号）
ll dp[MAXN][2];
ll dx[5]={1,11,111,1111};
// 其实正推还是比较难的，但是可以倒推（记忆化搜索）
// ll dfs(ll x){
// ll res=0;
//
// FOR(i,2,sqrtl(x)){
// if(x%i==0){
//
// }
// }
// }
inline void solve(){
cin>>N;
FOR(i,1,N){
dp[i][1]=INF;
dp[i][0]=INF;
}
// dfs(N);
dp[1][1]=1;
dp[1][0]=1;
dp[11][1]=2;
dp[11][0]=2;
dp[111][1]=3;
dp[111][0]=3;
dp[1111][1]=4;
dp[1111][0]=4;
FOR(i,2,N){
// dp[i]=dp[i-1]
FOR(j,2,sqrtl(i)){ // 乘法
if(i%j==0){
// 一个乘号
dp[i][1]=min({dp[j][1]+dp[i/j][1]+1,dp[i][1],
// 一个乘号+一对括号 一个乘号+两对对括号
dp[j][0]+dp[i/j][1]+3,dp[j][1]+dp[i/j][0]+3,dp[j][0]+dp[i/j][0]+5});
}
}
FOR(j,1,i-1){
// 就是一个加号嘛
dp[i][0]=min({dp[i][0],dp[j][0]+dp[i-j][0]+1,
dp[j][0]+dp[i-j][1]+1,dp[j][1]+dp[i-j][1]+1,dp[j][1]+dp[i-j][0]+1});
}
// ROF(j,N-1,2){
//
// }
}
cout<<min(dp[N][0],dp[N][1])<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>T;
// while(T--){
// solve();
// }
solve();
return 0;
}
/*
*/
```
:::
那么我们异想天开一点，直接转移字符串那
::: 转移字符串的程序
```cpp
FOR(j,2,sqrtl(i)){ // 乘法
if(i%j==0){
// 一个乘号
dp[i][1]=min({dp[i][1],dp[j][1]+"*"+dp[i/j][1],
"("+dp[j][0]+")"+"*"+dp[i/j][1],
dp[j][1]+"*"+"("+dp[i/j][0]+")",
"("+dp[j][0]+")"+"*"+"("+dp[i/j][0]+")"},comPareLen );
}
}
FOR(j,1,i-1){
// 就是一个加号嘛
dp[i][0]=min({dp[i][0],dp[j][0]+"+"+dp[i-j][0],
dp[j][0]+"+"+dp[i-j][1],dp[j][1]+"+"+dp[i-j][1],
dp[j][1]+"+"+dp[i-j][0] },comPareLen);
}
dp[i][1]=min(dp[i][1],"("+dp[i][0]+")",comPareLen);
```
:::
## AC代码
::: 源代码
```cpp
// Problem: F - Shortest One Formula
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
const string INFstr=string(1003,'a');
ll N,M,K,T;
// [0]是用加法拼出来的,[1]是用乘法拼出来的，或者不用加括号（这个属性会影响括号）
string dp[MAXN][2];
ll dx[5]={1,11,111,1111};
// 其实正推还是比较难的，但是可以倒推（记忆化搜索）
// ll dfs(ll x){
// ll res=0;
//
// FOR(i,2,sqrtl(x)){
// if(x%i==0){
//
// }
// }
// }
inline bool comPareLen(const string &a,const string &b){
return SZ(a)<SZ(b);
}
inline void solve(){
cin>>N;
FOR(i,1,N){
dp[i][1]=INFstr;
dp[i][0]=INFstr;
}
// dfs(N);
dp[1][1]="1";
dp[1][0]="1";
dp[11][1]="11";
dp[11][0]="11";
dp[111][1]="111";
dp[111][0]="111";
dp[1111][1]="1111";
dp[1111][0]="1111";
FOR(i,2,N){
if(i==11 || i==111 || i==1111) continue;
// dp[i]=dp[i-1]
FOR(j,2,sqrtl(i)){ // 乘法
if(i%j==0){
// 一个乘号
dp[i][1]=min({dp[i][1],dp[j][1]+"*"+dp[i/j][1],
"("+dp[j][0]+")"+"*"+dp[i/j][1],
dp[j][1]+"*"+"("+dp[i/j][0]+")",
"("+dp[j][0]+")"+"*"+"("+dp[i/j][0]+")"},comPareLen );
}
}
FOR(j,1,i-1){
// 就是一个加号嘛
dp[i][0]=min({dp[i][0],dp[j][0]+"+"+dp[i-j][0],
dp[j][0]+"+"+dp[i-j][1],dp[j][1]+"+"+dp[i-j][1],
dp[j][1]+"+"+dp[i-j][0] },comPareLen);
}
dp[i][1]=min(dp[i][1],"("+dp[i][0]+")",comPareLen);
// ROF(j,N-1,2){
//
// }
#ifdef LOCAL
cerr<<"i:"<<i<<" "<<dp[i][0]<<'\n';
cerr<<"i:"<<i<<" "<<dp[i][1]<<'\n';
cerr<<"\n";
#endif
}
cout<<min(dp[N][0],dp[N][1],comPareLen)<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>T;
// while(T--){
// solve();
// }
solve();
return 0;
}
/*
AC https://atcoder.jp/contests/abc403/submissions/65417394
(1+1)*(1+1+1)*((1+1)*(1+1+1)*11+1)+1
1+(1+1+1)*(1+11+11+111)
*/
```
:::
## 心路历程（WA，TLE，MLE……）