15 气球狂欢节
Time Limit:1000MS Memory Limit:65535K
题型: 编程题 语言: G++;GCC
描述：
一个充满魔法的国度中，存在一场年度的节日，名为“气球狂欢节”。在这个节日中，有一个传统的比赛，那就是“气球挑战赛”。在比赛中，参赛者面对一排魔法气球 （总共n个，1 <= n <= 10），每个气球内部都封印着一定数量的金币（金币至少为１个）。每个气球上都标记着一个数字，代表着封印的金币数。
参赛者的目标是通过戳破所有气球来收集金币。当一个气球被戳破时，参赛者可以根据一个特殊的魔法公式获得金币：金币 = 左侧气球的金币数 × 当前气球的金币数 × 右侧气球的金币数。如果左侧或右侧没有气球了，那么这个位置的金币数视为1（注：被戳破的气球所在位置视为不再有气球，这之后，该位置的金币数视为1）。
比赛的难点在于选择戳破气球的顺序，使得总共可以获得的金币数量最大化。现在，作为一位智慧的策略家，你的任务是帮助一位参赛者制定一个戳气球的策略，使得他可以获得尽可能多的金币。
输入格式：
第一行为气球的个数n， 1 <= n <= 10， 第二行开始为按顺序排列的气球所代表的金币数（均为正整数）。
输出格式：
输出戳破所有气球得到的最大金币数。（注：该题的结果不会超过20亿）
输入样例：
3
2 1 3
输出样例：
11
解释：
先戳破第2个气球，此时金币为2 × 1 × 3，再戳破第1个气球，此时金币为 1 × 2 × 1，再戳破第3个气球，金币为1 ×３×１，总金币为６ ＋ 2 ＋ ３ = 11
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <map>
#include <set>using namespace std;int n;
int mx=0;
int a[13];
int vis[13];
void dfs(int m,int ans)
{if(m>n){mx=max(ans,mx);return;}for(int i=1;i<=n;i++){if(vis[i]==1)continue;if(vis[i]!=1){vis[i]=1;int tmp=a[i];a[i]=1;dfs(m+1,ans+a[i-1]*tmp*a[i+1]);vis[i]=0;a[i]=tmp;}}
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];a[0]=a[n+1]=1;dfs(1,0);cout<<mx;
}
)