A45687. 42点42 是：· 组合数学上的第 5 个卡特兰数· 字符'*'的 ASCII 码· 钼的原子序数· 6 与 9 的乘积结果的 13 进制表示· 生命、 宇宙以及任何事情的终极答案· 以及……表达式(1+5)/2*(6-4)*7 的值因此， 小机器人 Marvin 发明了这个叫 42 点的小游戏。在这个游戏中，玩家会获得 n 个数。 玩家需要使用'+'、 '-'、 '*'、 '/'、 '('、 …
填空题
困难
知识点
题目描述
42点
42 是：
· 组合数学上的第 5 个卡特兰数
· 字符'*'的 ASCII 码
· 钼的原子序数
· 6 与 9 的乘积结果的 13 进制表示
· 生命、 宇宙以及任何事情的终极答案
· 以及……表达式(1+5)/2*(6-4)*7 的值
因此， 小机器人 Marvin 发明了这个叫 42 点的小游戏。在这个游戏中，玩家会获得 n 个数。 玩家需要使用'+'、 '-'、 '*'、 '/'、 '('、 ')'以及这 n 个数构成一个合法的中缀表达式， 并使得该表达式的值为 42。 n 个数之间的顺序可以改变。 表达式运算过程中只能出现整数。由于过于抑郁， Marvin 无力完成这个游戏， 于是来找你帮忙。 你的任务是对于给定的 n 个数， 判断他们是否能根据上述游戏规则算出 42。
时间限制： 1000
内存限制： 65536
输入
第一行为一个数 n， 1<=n<=6。 第二行为 n 个数， 每个数均为[1,13]范围内的整数。
输出
输出一行， 若可以算出 42 则输出“YES”， 否则输出“NO”（注意大小写）。
样例输入
6
1 5 2 6 4 7
样例输出
YES
参考答案
#include <cstdio>
#include <string>
#include <memory.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include<queue>
#include <set>
using namespace std;
set<int> dp[7][7];
int num[7],n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &num[i]);
dp[i][i].insert(num[i]);
}
int sum = 1;
for (int i = 2; i <= n; i++)
sum += i;
for (int _case = 1; _case <= sum; _case++) {
next_permutation(num, num + n);
for(int i=2;i<=n;i++)
for (int j = 1; j <= n - i + 1; j++) {
for (int k = j; k <= j+i-2; k++) {
for(auto ii=dp[j][k].begin();ii!=dp[j][k].end();ii++)
for (auto jj = dp[k + 1][j + i - 1].begin(); jj != dp[k + 1][j + i - 1].end(); jj++) {
dp[j][j + i - 1].insert(*ii + *jj);
dp[j][j + i - 1].insert(abs(*ii - *jj));
dp[j][j + i - 1].insert(*ii * *jj);
if (*jj != 0 && (*ii / (*jj)*(*jj)) == *ii)
dp[j][j + i - 1].insert(*ii / (*jj));
}
}
}
}
if (dp[1][n].find(42) != dp[1][n].end())
printf("YES\n");
else
printf("NO\n");
return 0;
}
上一题
下一题