多角形游戏（递归法）
多边形游戏（递归法）
此为简化问题,无须动态规划怎么完成
一个多边形，开始有n个顶点。每个顶点被赋予一个正整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
现在来玩一个游戏，该游戏共有n步：
第1步，选择一条边，将其删除
随后n-1步，每一步都按以下方式操作：（1）选择一条边E以及由E连接着的2个顶点v1和v2； (2）用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2，将顶点v1和v2的整数值通过边E上的运算得到的结果值赋给新顶点。
最后，所有边都被删除，只剩一个顶点，游戏结束。游戏得分就是所剩顶点上的整数值。那么这个整数值最大为多少？
关于输入
第一行为多边形的顶点数n（n≤20），其后有n行，每行为一个整数和一个字符，整数为顶点上的正整数值，字符为该顶点到下一个顶点间连边上的运算符“+”或“*”（最后一个字符为最后一个顶点到第一个顶点间连边上的运算符）。
关于输出
输出仅一个整数，即游戏所计算出的最大值。
例子输入
4
4 *
5 +
5 +
3 +
例子输出
70
------解决思路----------------------
http://bbs.****.net/topics/390910539
此为简化问题,无须动态规划怎么完成
一个多边形，开始有n个顶点。每个顶点被赋予一个正整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
现在来玩一个游戏，该游戏共有n步：
第1步，选择一条边，将其删除
随后n-1步，每一步都按以下方式操作：（1）选择一条边E以及由E连接着的2个顶点v1和v2； (2）用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2，将顶点v1和v2的整数值通过边E上的运算得到的结果值赋给新顶点。
最后，所有边都被删除，只剩一个顶点，游戏结束。游戏得分就是所剩顶点上的整数值。那么这个整数值最大为多少？
关于输入
第一行为多边形的顶点数n（n≤20），其后有n行，每行为一个整数和一个字符，整数为顶点上的正整数值，字符为该顶点到下一个顶点间连边上的运算符“+”或“*”（最后一个字符为最后一个顶点到第一个顶点间连边上的运算符）。
关于输出
输出仅一个整数，即游戏所计算出的最大值。
例子输入
4
4 *
5 +
5 +
3 +
例子输出
70
------解决思路----------------------
//http://bbs.****.net/topics/390893174
//多边形游戏
//描述
// 一个多边形，开始有n个顶点。每个顶点被赋予一个正整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
// 现在来玩一个游戏，该游戏共有n步：
// 第1步，选择一条边，将其删除
// 随后n-1步，每一步都按以下方式操作：
// （1）选择一条边E以及由E连接着的2个顶点v1和v2；
// （2）用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2，将顶点v1和v2的整数值通过边E上的运算得到的结果值赋给新顶点。
// 最后，所有边都被删除，只剩一个顶点，游戏结束。游戏得分就是所剩顶点上的整数值。那么这个整数值最大为多少？
//输入
// 第一行为多边形的顶点数n（n ≤ 20），其后有n行，每行为一个整数和一个字符，
// 整数为顶点上的正整数值，字符为该顶点到下一个顶点间连边上的运算符“+”或“*”
// （最后一个字符为最后一个顶点到第一个顶点间连边上的运算符）。
//输出
// 输出仅一个整数，即游戏所计算出的最大值。
//样例输入
//4
//4 *
//5 +
//5 +
//3 +
//样例输出
//70
//提示
//小规模问题可不必用动态规划方法编程求解，仅用递归就可以求解。
//计算中不必考虑计算结果超出整数表达范围的问题，给出的数据能保证计算结果的有效性。
//在给的例子中，计算过程为(3+4)*(5+5)=70。
#include <stdio.h>
int d[20],e[20],o[20];
char r[20];
char b[2];
char c;
int i,n,s;
int maxv;
int next_pl(int * f, int * l) {
int t;
int *ff,*ll,*i,*p,*j;
i = l;
if (f == l
------解决思路----------------------
f == --i) return (0);
while (1) {
p = i;
if (*--i < *p) {
j = l;
while (1) {
j--;
if (*i<*j) break;//
}
t=*i;*i=*j;*j=t;
ff=p;
ll=l;
for (; ff < ll; ++ff) {
ll--;
t=*ff;*ff=*ll;*ll=t;
}
return (1);
}
if (i == f) {
ff=f;
ll=l;
for (; ff < ll; ++ff) {
ll--;
t=*ff;*ff=*ll;*ll=t;
}
return (0);
}
}
}
void merge(int f) {//合并计算顶点f和f+1,并将结果覆盖到f和f+1
int t;
t=(f+1)%n;
switch (r[f]) {
case '+':
printf("e[%d]%ce[%d]=%d%c%d",f,r[f],t,e[f],r[f],e[t]);
e[f]=e[f]+e[t];
e[t]=e[f];
printf("=%d\n",e[f]);
break;
case '*':
printf("e[%d]%ce[%d]=%d%c%d",f,r[f],t,e[f],r[f],e[t]);
e[f]=e[f]*e[t];
e[t]=e[f];
printf("=%d\n",e[f]);
break;
}
}
void play(int s) {//从第s(0..n-1)个顶点开始,递归计算其后n-1条边消除的所有方案
int j,v;
for (j=0;j<n-1;j++) o[j]=j;
do {
for (j=0;j<n;j++) e[j]=d[j];
printf("o[]=");
for (j=0;j<n-1;j++) printf("%d",o[j]);
printf("\n");
for (j=0;j<n-1;j++) merge((s+o[j])%n);
v=e[(s+o[n-2])%n];
printf("v=%d\n",v);
if (maxv<v) maxv=v;
} while (next_pl(&o[0],&o[0]+n-1));//此处用全排列是有问题的。
//应参考nkh_all3.cpp中的算法
//用递归的方法遍历计算比如等式3+4*5+5的所有运算顺序：
//(((3+4)*5)+5)
//((3+(4*5))+5)
//(3+((4*5)+5))
//(3+(4*(5+5)))
//((3+4)*(5+5))
}
int main() {
scanf("%d",&n);
for (i=0;i<n;i++) {
scanf("%d%1s",&d[i],b);
r[i]=b[0];
}
maxv=0;
for (s=0;s<n;s++) {
c=r[s];
r[s]=' ';
play((s+1)%n);
r[s]=c;
}
printf("maxv=%d\n",maxv);
return 0;
}
//4
//4 *
//5 +
//5 +
//3 +
//o[]=012
//e[1]+e[2]=5+5=10
//e[2]+e[3]=10+3=13
//e[3]+e[0]=13+4=17
//v=17
//o[]=021
//e[1]+e[2]=5+5=10
//e[3]+e[0]=3+4=7
//e[2]+e[3]=10+7=17
//v=17
//o[]=102
//e[2]+e[3]=5+3=8
//e[1]+e[2]=5+8=13
//e[3]+e[0]=8+4=12 ←由于错误地使用全排列算法，此处计算错误。应为e[3]+e[0]=13+4=17。下面还有类似错误。
//v=12
//o[]=120
//e[2]+e[3]=5+3=8
//e[3]+e[0]=8+4=12
//e[1]+e[2]=5+8=13
//v=13
//o[]=201
//e[3]+e[0]=3+4=7
//e[1]+e[2]=5+5=10
//e[2]+e[3]=10+7=17
//v=17
//o[]=210
//e[3]+e[0]=3+4=7
//e[2]+e[3]=5+7=12
//e[1]+e[2]=5+12=17
//v=17
//o[]=012
//e[2]+e[3]=5+3=8
//e[3]+e[0]=8+4=12
//e[0]*e[1]=12*5=60
//v=60
//o[]=021
//e[2]+e[3]=5+3=8
//e[0]*e[1]=4*5=20
//e[3]+e[0]=8+20=28
//v=28
//o[]=102
//e[3]+e[0]=3+4=7
//e[2]+e[3]=5+7=12
//e[0]*e[1]=7*5=35
//v=35
//o[]=120
//e[3]+e[0]=3+4=7
//e[0]*e[1]=7*5=35
//e[2]+e[3]=5+7=12
//v=12
//o[]=201
//e[0]*e[1]=4*5=20
//e[2]+e[3]=5+3=8
//e[3]+e[0]=8+20=28
//v=28
//o[]=210
//e[0]*e[1]=4*5=20
//e[3]+e[0]=3+20=23
//e[2]+e[3]=5+23=28
//v=28
//o[]=012
//e[3]+e[0]=3+4=7
//e[0]*e[1]=7*5=35
//e[1]+e[2]=35+5=40
//v=40
//o[]=021
//e[3]+e[0]=3+4=7
//e[1]+e[2]=5+5=10
//e[0]*e[1]=7*10=70
//v=70
//o[]=102
//e[0]*e[1]=4*5=20
//e[3]+e[0]=3+20=23
//e[1]+e[2]=20+5=25
//v=25
//o[]=120
//e[0]*e[1]=4*5=20
//e[1]+e[2]=20+5=25
//e[3]+e[0]=3+20=23
//v=23
//o[]=201
//e[1]+e[2]=5+5=10
//e[3]+e[0]=3+4=7
//e[0]*e[1]=7*10=70
//v=70
//o[]=210
//e[1]+e[2]=5+5=10
//e[0]*e[1]=4*10=40
//e[3]+e[0]=3+40=43
//v=43
//o[]=012
//e[0]*e[1]=4*5=20
//e[1]+e[2]=20+5=25
//e[2]+e[3]=25+3=28
//v=28
//o[]=021
//e[0]*e[1]=4*5=20
//e[2]+e[3]=5+3=8
//e[1]+e[2]=20+8=28
//v=28
//o[]=102
//e[1]+e[2]=5+5=10
//e[0]*e[1]=4*10=40
//e[2]+e[3]=10+3=13
//v=13
//o[]=120
//e[1]+e[2]=5+5=10
//e[2]+e[3]=10+3=13
//e[0]*e[1]=4*10=40
//v=40
//o[]=201
//e[2]+e[3]=5+3=8
//e[0]*e[1]=4*5=20
//e[1]+e[2]=20+8=28
//v=28
//o[]=210
//e[2]+e[3]=5+3=8
//e[1]+e[2]=5+8=13
//e[0]*e[1]=4*13=52
//v=52
//maxv=70
//
http://bbs.****.net/topics/390910539