写出满足如下条件的C++代码:无优先级运算问题 输入格式: 第一行输入正整数n和整数m 第二行输入具体的n个正整数。 输出格式: 第一行输出最少运算次数。 第二行输出对应的运算表达式。若输入的n个正整数无法运算得到m,则输出“-1”。
时间: 2024-03-20 09:39:31 浏览: 65
c++输入一个整数,输出一个整数
以下是满足条件的C++代码:
```cpp
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 105;
int n, m, a[MAXN];
int dp[MAXN][MAXN][MAXN], pre[MAXN][MAXN][MAXN];
void print_expression(int l, int r, int v, vector<char>& op) {
if (l == r) {
cout << a[l];
return;
}
int k = pre[l][r][v];
if (k == -1) {
cout << "(";
print_expression(l, r - 1, v - a[r], op);
cout << "+";
print_expression(r, r, a[r], op);
cout << ")";
} else {
cout << "(";
print_expression(l, k, dp[l][r][v], op);
for (int i = k + 1; i <= r; i++) {
cout << op[i];
if (i == r) {
print_expression(i, i, a[i], op);
} else {
print_expression(i, r, v, op);
}
}
cout << ")";
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
memset(dp, -1, sizeof(dp));
dp[1][n][0] = 0;
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int v = 0; v <= m; v++) {
if (dp[l][r][v] != -1) {
continue;
}
int res = -1;
for (int k = l; k < r; k++) {
if (dp[l][k][v] != -1 && dp[k + 1][r][v] != -1) {
int cnt = dp[l][k][v] + dp[k + 1][r][v];
if (res == -1 || cnt < res) {
res = cnt;
pre[l][r][v] = k;
}
}
if (v >= a[r] && dp[l][r - 1][v - a[r]] != -1) {
int cnt = dp[l][r - 1][v - a[r]] + 1;
if (res == -1 || cnt < res) {
res = cnt;
pre[l][r][v] = -1;
}
}
}
dp[l][r][v] = res;
}
}
}
if (dp[1][n][m] == -1) {
cout << "-1" << endl;
} else {
vector<char> op(n + 1);
print_expression(1, n, m, op);
cout << endl;
}
return 0;
}
```
该程序使用动态规划算法求解无优先级运算问题。具体来说,设 $dp[l][r][v]$ 表示区间 $[l,r]$ 内的数可以通过运算得到 $v$ 的最少运算次数。我们枚举 $[l,r]$ 以及 $v$,考虑如何转移。对于任意的 $l \leq k < r$,我们可以把区间 $[l,r]$ 拆成区间 $[l,k]$ 和 $[k+1,r]$ 两部分,分别计算它们得到的值,然后把它们合并起来。这样的话,合并操作需要进行一次加法运算,因此需要进行 $dp[l][k][v]$ 次运算和 $dp[k+1][r][v]$ 次运算。如果区间 $[l,r]$ 的最后一个数为 $a_r$,我们也可以把它拆分出来单独计算,这样需要进行 $dp[l][r-1][v-a_r]$ 次运算和 $1$ 次加法运算。以上两种情况中取最小值即为 $dp[l][r][v]$ 的值。在转移的过程中记录路径即可得到运算表达式。
阅读全文