蓝桥杯-算法训练 Lift and Throw 求教各位大牛，谢谢各位

Question

问题描述
　　给定一条标有整点(1, 2, 3, ...)的射线. 定义两个点之间的距离为其下标之差的绝对值.
　　Laharl, Etna, Flonne一开始在这条射线上不同的三个点, 他们希望其中某个人能够到达下标最大的点.
　　每个角色只能进行下面的3种操作, 且每种操作每人不能进行超过一次.

　　1.移动一定的距离
　　2.把另一个角色高举过头
　　3.将举在头上的角色扔出一段距离

　　每个角色有一个movement range参数, 他们只能移动到没有人的位置, 并且起点和终点的距离不超过movement range.
　　如果角色A和另一个角色B距离为1, 并且角色B没有被别的角色举起, 那么A就能举起B. 同时, B会移动到A的位置,B原来所占的位置变为没有人的位置

. 被举起的角色不能进行任何操作, 举起别人的角色不能移动.同时, 每个角色还有一个throwing range参数, 即他能把举起的角色扔出的最远的距离.

注意, 一个角色只能被扔到没有别的角色占据的位置. 我们认为一个角色举起另一个同样举起一个角色的角色是允许的. 这种情况下会出现3个人在同一

个位置的情况. 根据前面的描述, 这种情况下上面的两个角色不能进行任何操作, 而最下面的角色可以同时扔出上面的两个角色. 你的任务是计算这些角

色能够到达的位置的最大下标, 即最大的数字x, 使得存在一个角色能够到达x.
输入格式
　　输入共三行, 分别为Laharl, Etna, Floone的信息.
　　每一行有且仅有3个整数, 描述对应角色的初始位置, movement range, throwing range.
　　数据保证3个角色的初始位置两两不相同且所有的数字都在1到10之间.
输出格式
　　仅有1个整数, 即Laharl, Etna, Flonne之一能到达的最大距离.
样例输入
9 3 3
4 3 1
2 3 3
样例输出
15
样例说明
　　一开始Laharl在位置9, Etna在位置4, Flonne在位置2.
　　首先, Laharl移动到6.
　　然后Flonne移动到位置5并且举起Etna.
　　Laharl举起Flonne将其扔到位置9.
　　Flonne把Etna扔到位置12.
　　Etna移动到位置15.
原题地址：http://lx.lanqiao.org/problem.page?gpid=T356
希望各位能解答一下，最好能提供一下思路和源代码，感激不尽

Answer 1

 #include<iostream>
#include<cstring>
using namespace std;
int x=0; //记录最大值 
int flag[43]; //辅助数组由题可知10 10 10 9 10 10 8 10 10这样最大的数据所能走的最大距离为43所有下标43够了
int N[]={0,1,2,3,4,5,6,7,8}; //辅助九个动作全排列数组
struct 
{
int pos; //此人当前所在的位置
int flag; //如果flag为0代表没被举 1代表被举了
int juren;
int mvflag;     //移动标志位如果没移动则为0 移动了则为1
int mvmax;  //移动的最大步数
int thrflag;  //丢标志位丢过为1没丢过则为0
int thrmax;  //丢的最大距离 
}People[3];   //三个人 
void swap(int a,int b)
{
int temp=N[a];
N[a]=N[b];
N[b]=temp;
}
void judge(int a,int b,int pos)
{
switch(People[0].thrflag+People[1].thrflag+People[2].thrflag) //0代表第一次丢人的人不用去判断走.1代表第二次丢 2代表第三次丢 
{
case 1: if(People[a].mvflag==0)//如果背人的这个没走过且是第二次丢人
 x=x>pos+People[a].mvmax+1+People[b].thrmax?x:pos+People[a].mvmax+1+People[b].thrmax;  //这里有个比较巧的事情 
break;
case 2: if(People[a].mvflag==0)//如果背人的这个没走过且是第三次丢人 
if(People[a].mvmax>People[a].thrmax)
 x=x>pos+People[a].mvmax?x:pos+People[a].mvmax; 
if(People[b].mvflag==0)//如果被扔的人还能走则计算一下最远距离
x=x>pos+People[a].thrmax+People[b].mvmax?x:pos+People[a].thrmax+People[b].mvmax;
break;
}
}
void Permutations(int n)
{
for(int i=n;i<9;i++)
{
swap(i,n);
int p=N[n]/3; 
//当前动作的人0-2为第一个人的动作一次类推
int pos=People[p].pos;//此人当前所在位置 
int j;
switch(N[n]%3)//根据动作的不同选择该人需要做的事 当前动作？0为移动1为举2为扔
{
case 0: 
if(People[p].flag||People[p].juren)break; 
//如果被举或者举了人都不能移动直接退出
x=x>pos+People[p].mvmax?x:pos+People[p].mvmax;//当前位置加上移动最大值如果大于原值则替换
for(j=1;j<=People[p].mvmax;j++)//逐步往后移动 
{
if(flag[pos+j]==0)//如果可以移动才移动 
{
flag[pos]=0;  //原位置清0
flag[pos+j]=p+1;//下一位置为该人下标+1 
People[p].pos=pos+j; 
//此人当前位置变为移动后的位置 
People[p].mvflag=1; 
//1代表移动过了
Permutations(n+1); 
People[p].mvflag=0;//所有状态回朔
flag[pos+j]=0; 
flag[pos]=p+1; 
People[p].pos=pos; 

}
} 
for(j=1;j<=People[p].mvmax;j++)//逐步往前移动  
{
if(pos-j>0&&flag[pos-j]==0) //可以移动且大于0
{
flag[pos]=0;  //原位置清0
flag[pos-j]=p+1;//下一位置为该人下标 
People[p].pos=pos-j; 
//此人当前位置变为移动后的位置 
People[p].mvflag=1; 
//1代表移动过了
Permutations(n+1); 
People[p].mvflag=0; 
flag[pos-j]=0;//所有状态回朔 
flag[pos]=p+1; 
People[p].pos=pos; 

} 
}
break;
case 1:
if(People[p].flag==1)break;   
//如果此人被举则不能举别人直接退出因为是全排列计算不会出现此人举过再举
if(flag[pos+1]!=0)//后面有人则先举后面的 
{
People[p].juren=flag[pos+1];  //举了这个人
People[flag[pos+1]-1].flag=1 ;//被举人状态变为被举 
flag[pos+1]=0;//后面的人被举了之后位置清0
Permutations(n+1);
flag[pos+1]=People[p].juren;//回朔
People[p].juren=0;   
People[flag[pos+1]-1].flag=0 ;
People[flag[pos+1]-1].pos=pos+1; //位置复位 
} 
if(flag[pos-1]!=0&&pos-1>0)//原理同上举后面的人 
{
People[p].juren=flag[pos-1];  //举了这个人
People[flag[pos-1]-1].flag=1 ;//被举人状态变为被举 
flag[pos-1]=0;//后面的人被举了之后位置清0
Permutations(n+1);
flag[pos-1]=People[p].juren;//回朔
People[p].juren=0;   
People[flag[pos-1]-1].flag=0 ;
People[flag[pos-1]-1].pos=pos-1; //位置复位 
}
break;
case 2:
if(People[p].juren==0||People[p].flag==1)break; //如果没举人或者被别人举了则不能扔直接退出 
x=x>pos+People[p].thrmax?x:pos+People[p].thrmax;
int juren=People[p].juren-1;//-1之后 才是此人操作的下标 
judge(p,juren,pos);  //这个函数是整个裁剪的关键部分，处理之后可以让丢过人的人不用再走而得到最大距离
for(j=1;j<=People[p].thrmax;j++)
{
if(flag[pos+j]==0)//丢原理和移动类似 
{
People[juren].pos=pos+j;  //被丢人的位置变为丢到的位置 这里有一个地方没有清0就是背人标记位，从而减少了不必要的移动。
People[juren].flag=0;     //被举状态复位
flag[pos+j]=juren+1; //标记位置信息
People[p].thrflag=1; //状态变为扔过人 
Permutations(n+1); 
People[p].thrflag=0; //回朔 
People[juren].flag=1;     //被举状态复位
flag[pos+j]=0; //标记位置信息
}
}
for(j=1;j<=People[p].thrmax;j++)
{
if(flag[pos-j]==0&&pos-j>0)//丢原理和移动类似 
{
People[juren].pos=pos-j;  //被丢人的位置变为丢到的位置
People[juren].flag=0;     //被举状态复位
flag[pos-j]=juren+1; //标记位置信息
People[p].thrflag=1; 
Permutations(n+1); 
People[p].thrflag=0; 
 //回朔 
People[juren].flag=1;     //被举状态复位
flag[pos-j]=0; //标记位置信息
}
}
break;
} 
swap(i,n); //回朔 
}
}
int main()
{
int i,j;
x=0;
memset(flag,0,sizeof(flag));
memset(People,0,sizeof(People));
for(i=0;i<3;i++)
{
cin>>People[i].pos>>People[i].mvmax>>People[i].thrmax; //输入位置信息以及丢和扔的最大距离
flag[People[i].pos]=i+1; 
//将位置绑定为当前人 因为0代表没人所以人下标加1 
}
Permutations(0);//9个动作递归全排列计算
cout<<x<<endl;
return 0;
}