lift and throw-藍橋杯-算法訓練 Lift and Throw 求教各位大牛，謝謝各位

藍橋杯-算法訓練 Lift and Throw 求教各位大牛，謝謝各位

問題描述
　　給定一條標有整點(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
希望各位能解答一下，最好能提供一下思路和源代碼，感激不盡

最佳回答：

 #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;
}