3.5　相关题库

【3.5.1　Transportation】

Ruratania在包括运输业在内的多个领域中，正在建立新型的企业化的运作机制。运输公司TransRuratania要开设从城市A到城市B的一趟新的特快列车，途中要停若干站。车站依次编号，城市A编号为0，城市B编号为m。公司要进行一项实验，以改进乘客的运输量，并增加其收入。这列火车的最大容量为n位乘客。火车票的价格等于出发站和目的地站（包括目的地站）之间的停车次数（也就是站的数量）。在列车从城市A出发之前，从线路上所有站订票的信息已经被获取完毕。一份车站S的订票订单是从车站S出发到一个确定的目的地站的所有预订。如果因为乘客容量的限制，公司有可能不能接受所有的订单，公司的策略是，对于每个站的每一份订票订单，要么完全接受，要么完全拒绝。

请编写一个程序，基于城市A到城市B的线路上的车站给出的订单，确定TransRuratania公司最大可能的总收入。一个被接受订单的收入是订单中乘客的数量和他们的车票价格的乘积。公司总收入则是所有被接受的订单收入的总和。

输入

输入被划分为若干个测试用例。每个测试用例的第一行包含3个整数：列车乘客的最大容量n、城市B的编号和所有车站被预订的车票总数。下面的行给出订票订单。每份订单包含3个整数：出发站、目的地站和乘客数量。在每个测试用例中，最多有22份订单，城市B编号最多为7。测试用例以第一行的3个整数全部取0作为输入结束。

输出

除输入结束标志以外，对每个测试用例，输出一行，每行给出最大可能的总收入。

试题来源：ACM Central European Regional Contest 1995

在线测试：POJ 1040，UVA 301

提示

显而易见，本题应采用回溯法求解。

（1）回溯搜索前的预处理

最大收入best，初始时为0；订单数，即所有车站被预订的车票总数为count。

订单序列为orders[]，其中第i份订单的起始站为orders[i].from，目的地站为orders[i].to，旅客数为orders[i].passangers。若公司接受该订单，则收入为orders[i].price=(orders[i].to-orders[i].from)*orders[i].passangers（0≤i≤count-1）。

我们以price域为关键字，按递增顺序排列订单序列orders[]。计算接受剩余订单的收入总和orders[i].remaining=，该域在回溯算法中列为最优性条件。回溯搜索时，我们按照orders[]的顺序枚举每份订单。

车站序列为train[]，其中车站i的旅客数为train[i]，初始时train[]清零。

（2）回溯搜索

我们按照接受订单的收入递增顺序搜索每份订单。

状态：求解过程中每一步的状况为当前订单start，已接受的订单收入为earnings，这两个参数被列为递归过程的值参(start，earnings)。另外，各个车站的人数train[]也为状态，因为公司一旦接受订单，则需要累计途经火车站的人数，判断是否超载，回溯时需要恢复订单接受前途经火车站的人数。为了避免内存溢出，train[]为全局变量。

最优目标状态的条件earnings>best：若当前收入最大，则调整最大收入（best=earnings）。

搜索范围为start≤k≤count-1。

订单k是否被接受，需要同时满足约束条件和最优性要求。

最优性要求earnings+orders[k].remaining<best：若即使按收入最大化要求，全部接受剩余订单也不可能更优，则拒绝k订单，回溯；否则进行判断。

约束条件：订单k途经的每个火车站i（orders[k].from≤i≤orders[k].to-1）增加了订单k的旅客后没有超载，即train[i]+=orders[k].passangers)≤n。

·若不满足约束条件，则拒绝订单k，恢复先前订单k途经的每个火车站人数（for(;i>=orders[k].from;i--)train[i]-=orders[k].passangers）。

·若满足约束条件，则接受订单k，递归子状态(k+1,earnings+orders[k].price)。回溯时，恢复订单start接受前各车站的人数（for(;i>=orders[k].from;i--)train[i]-=orders[k].passangers）。

显然，递归状态（0，0）后得出的best即问题解。

【3.5.2　Don’t Get Rooked】

在国际象棋中，车是一个可以纵向或横向移动任意个方格的棋子。本题我们仅考虑小棋盘（最多4×4），棋盘上还设置了若干堵墙，车无法通过墙。本题的目标是使棋盘上的车两两之间不能相互攻击对方。在棋盘上，一个合法的车的放置方法是没有两个车在同一水平行或垂直行，除非至少有一堵墙将它们分隔开。

图3.5-1给出了五张相同的棋盘。第一张图是空的棋盘，第二和第三张图给出了合法放置车的棋盘，而第四和第五张图则是非法放置车的棋盘。这张棋盘可以合法放置的车的最大数量是5；第二张图给出了一种放置方法，当然还有其他放置方法。

图　3.5-1

请编写一个程序，给出一张棋盘，计算在棋盘上可以合法放置车的最大数量。

输入

输入给出一张或多张棋盘的描述，然后在一行中给出数字0表示输入结束。每张棋盘的描述先在一行中给出一个正整数n，表示棋盘的大小，n最多为4。接下来的n行每行描述棋盘的一行，一个“.”表示一个可以放置车的方格，而大写字母“X”表示墙。输入中没有空格。

输出

对于每一个测试用例，输出一行，给出在棋盘上可以合法放置的车的最大数量。

试题来源：ACM Mid-Central USA 1998

在线测试：POJ 1315，UVA 639

提示

我们给每个棋格定义3个标志：

·“.”标志；

·合法放置车的“P”标志；

·墙标志“X”。

在计算棋盘上合法放置的最大车的数量前，做预处理：在棋盘的外围（0行、size+1行和0列）添加一堵墙（如图3.5-2所示）。

图　3.5-2

按由上而下、由左而右的顺序搜索每个棋格。显然，若越过(x,y)左方和上方连续个“.”格后遇到的第1个格是“X”格，则(x,y)是车的安全放置位置，标志(x,y)是“P”格；否则(x,y)不是车的安全放置位置。

我们可以通过回溯法计算棋盘上可合法放置的最大车数。设nPlaced为当前合法放置的车数，mostPlaced为可放置的最多车数，初始时mostPlaced为0。

状态：求解过程中每一步的状况包括：

·当前格(x,y)，该参数被列为递归过程的值参；

·棋盘board[][]，为了避免溢出，将其设为全局变量，回溯时需恢复递归前的状态。

搜索范围x≤n：按照自上而下的顺序搜索n行。

约束条件(x,y)是“.”格且为车的安全放置位置：若满足该约束条件，则(x,y)置“P”标志；递归(x,y+1)后得出的车数+1即当前方案合法放置的车nPlaced。若该车数为目前最大（nPlaced>mostPlaced），则调整mostPlaced=nPlaced。回溯时，需恢复递归前的棋盘状态，即恢复(x,y)递归前的“.”标志。

无论(x,y)是否满足约束条件，都需要计算下一个搜索位置：若y≥n，则下一个搜索位置为(x+1,1)；否则下一个搜索位置为(x,y+1)。

显然，从(1,1)格出发进行回溯搜索，便可计算出可放置的最多车数mostPlaced。

【3.5.3　8 Queens Chess Problem】

在国际象棋的棋盘上，可以放置8个皇后，使得没有一个皇后会被其他的皇后攻击。给出一个皇后的初始位置，请编写一个程序，确定所有可能的8个皇后的放置方法。

不要试图写一个程序计算8个皇后在棋盘上每一个可能的8种放置。这将要进行8⁸次的计算，会使系统崩溃。对于你的程序，会有一个合理的运行时间约束。

输入

程序的输入是用一个空格分隔开的两个数字。这些数字表示在棋盘上8个皇后中的一个所占据的位置。给出的棋盘是合法的，程序不需要对输入进行验证。

为了规范表示，本题设定棋盘左上角的位置是(1,1)。水平行最上面的行是第1行，垂直列最左边的列是第1列。如图3.5-3所示，方格(4,6)意味着第4行第6列。

图　3.5-3

输出

程序的输出是一行一个解答。

每个解答是1…N的数字序列。每个解由8个数字组成。这8个数字每一个都是解答的行坐标。列坐标按8个数字的顺序给出。也就是说，第1个数字是在第1列的皇后的行坐标，第2个数字是在第2列的皇后的行坐标，以此类推。

下述的样例输入产生4个解答，下面给出每个解答的完整的8×8表示。

如上所述，每个解答仅输出一行，用8个数字表示。解答1将皇后放置在第1行第1列，第5行第2列，第8行第3列，第6行第4列，第3行第5列，…，第4行第8列。

按样例输出所示，输出两行列标题，并按字典序输出解答。

试题来源：ACM East Central 1988

在线测试：UVA 750

提示

（1）离线计算8个皇后的所有放置方案

在确定一个皇后位置的情况下，其余7个皇后的放置方案有多种。我们不妨先离线计算出8个皇后的所有放置方案，将这些方案存放在一个记录表中。以后，每输入一个皇后位置(r，c)，就在记录表中查询所有含(r，c)的方案。

设方案数为l；方案记录表为sol[][]，其中sol[k][j]为第k个方案中位于第j列上皇后的行位置（0≤k≤l-1，0≤j≤7）；当前方案为temp[]，其中第i列上皇后的行位置为temp[i]（0≤i≤7）；行标志为row[]，其中row[i]=true标志第i行目前未放置皇后；左对角线标志为leftDiag[]，其中leftDiag[k]=true标志第k条左对角线目前未放置皇后，经过（r，c）的左对角线序号k=r+c；右对角线标志为rightDiag[]，其中rightDiag[k]=true标志第k条右对角线目前未放置皇后，经过(r，c)的右对角线序号k=c-r+8。计算左右对角线序号的思想方法可参阅例题【3.4.2 The Sultan’s Successors】。

我们采用回溯法计算8个皇后的所有放置方案。

状态：求解过程中每一步的状况包括：

·当前列c，该参数列为递归过程的值参。

·行标志row[]、左对角线标志leftDiag[]和右对角线标志rightDiag[]。为了避免溢出，将其设为全局变量，回溯时需恢复递归前的状态。

边界条件c==8：若8列搜索完，则第9列皇后的行位置设为0（temp[8]=0），当前方案记为第l个方案（strcpy(sol[l],temp)），下一个方案的序号l++，回溯（return）。

搜索范围0≤r≤7：若8列未搜索完，则按自上而下的顺序搜索c列的每一格。

约束条件(row[r] & & rightDiag[c-r+8] & & leftDiag[c+r])=true：若r行和经过(r,c)的左右对角线目前没有皇后，则设定r行和经过(r，c)的左右对角线有皇后标志（row[r]=rightDiag[c-r+8]=leftDiag[r+c]=false），(r，c)放置皇后（temp[c]=r），递归c+1列。回溯时，恢复递归前row[]、leftDiag[]和rightDiag[]的值（row[r]=rightDiag[c-r+8]=leftDiag[r+c]=true）。

显然从0列出发进行递归，便可得出8个皇后放置的方案记录表sol[][]。

（2）从方案记录表sol[][]中找出含皇后位置(r，c)的放置方案

每输入1个皇后位置（r，c），则检索方案记录表sol[][]：若sol[i]满足条件(sol[i][c-1]==r-1)=true，则sol[i][0]…sol[i][7]是含皇后位置(r，c)的一个放置方案（0≤i≤l-1）。