传奇网站架设教程,wordpress多专题模版,机械加工网站哪里找,响应式网站 模版题意#xff1a;
一排杂乱的牌#xff0c;牌间距为1#xff0c;每次移动只能将小的牌#xff0c;移动到较大牌上#xff0c;最终使得牌从小到大排好在一堆。问移动的最小距离。
题目#xff1a;
蜘蛛牌是windows xp操作系统自带的一款纸牌游戏#xff0c;游戏规则是这…题意
一排杂乱的牌牌间距为1每次移动只能将小的牌移动到较大牌上最终使得牌从小到大排好在一堆。问移动的最小距离。
题目
蜘蛛牌是windows xp操作系统自带的一款纸牌游戏游戏规则是这样的只能将牌拖到比她大一的牌上面A最小K最大如果拖动的牌上有按顺序排好的牌时那么这些牌也跟着一起移动游戏的目的是将所有的牌按同一花色从小到大排好为了简单起见我们的游戏只有同一花色的10张牌从A到10且随机的在一行上展开编号从1到10把第i号上的牌移到第j号牌上移动距离为abs(i-j)现在你要做的是求出完成游戏的最小移动距离。
Input
第一个输入数据是T表示数据的组数。 每组数据有一行10个输入数据数据的范围是[1,10]分别表示A到10我们保证每组数据都是合法的。
Output
对应每组数据输出最小移动距离。
Sample Input
1 1 2 3 4 5 6 7 8 9 10
Sample Output
9
思路
1.对移动牌的先后顺序进行枚举全排列当然要剪枝 2.其实这道题很简单但由于我忽略了break导致错误所以我来总结下此类搜索题的做法找某种最优情况1若为图一般用记忆化搜索2若为线性结构就基本上是全排列将所有情况排列出来找出最优解。由于复杂度比较大所以剪枝是比较重要的。 3 对本题来说我们只能将较小牌放到较大牌上若最优一定是某些段先结合最终得到一堆。所以类似全排列若最优只能让较小牌到达离他最近的没有标记过的较大牌故找到后需跳出循环。得到使某些段先结合的效果。 4 全排列的搜索模板
void dfs(int step)//step 表示当前在第几个位置
{int i;if(stepn1)//如果stepn1表示前n个数字已经放好 {for(i1;in;i)//输出一种全排列 printf(%d,a[i]);printf(\n);return; }for(i1;in;i) //每次搜索都从1-n 一一尝试 {if(book[i]0)//判断次数字是否用过 {a[step]i;//存储当前位置的数字以便满足条件输出 book[i]1;//当前数字已用过改变标志以防重用 dfs(step1);//放好当前位置数字之后安排下一个数字 book[i]0;//回溯当满足一种全排列后进行下一种尝试 }}return ;
}
dfs(1);AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int inf0x3f3f3f;
int a[20],ans,book[20];
void dfs(int step,int num)
{if(step9){ansnum;return ;}for(int i1; i10; i)if(!book[i]){book[i]1;for(int ji1; j10; j)if(!book[j]abs(a[j]-a[i])numans){dfs(step1,numabs(a[i]-a[j]));break;/*从位置i走到j只能是i到没有标记过的第一个j在递归过程中实现中间的某一段结合再从头到尾结合*/}book[i]0;}return ;
}
int main()
{int t;scanf(%d,t);while(t--){for(int i1; i10; i){int c;scanf(%d,c);a[c]i;}ansinf;memset(book,0,sizeof(book));dfs(0,0);printf(%d\n,ans);}return 0;
}
