题解：AT_abc403_f [ABC403F] Shortest One Formula

题目大意

给定一个数

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

CPP

#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;
}

题解：AT_abc403_f [ABC403F] Shortest One Formula

文章操作

题目大意

思路

code

相关推荐

评论

题解：AT_abc403_f [ABC403F] Shortest One Formula