The Sultan of Nubia has no children, so she has decided that the country will be split into up tokseparate parts on her death and each part will be inherited by whoever performs best at some test. It
is possible for any individual to inherit more than one or indeed all of the portions. To ensure that only highly intelligent people eventually become her successors, the Sultan has devised an ingenious test. In a large hall filled with the splash of fountains
and the delicate scent of incense have been placedkchessboards. Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 jewelled chess queens. The task facing each potential successor is to place the 8 queens
on the chess board in such a way that no queen threatens another one, and so that the numbers on the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (For those unfamiliar with the rules of chess, this implies that
each row and column of the board contains exactly one queen, and each diagonal contains no more than one.)
Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions. (You know that the Sultan is both a good chess player
and a good mathematician and you suspect that her score is the best attainable.)
Input
Input will consist ofk(the number of boards), on a line by itself, followed byksets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a positive integer
less than 100. There will never be more than 20 boards.
Output
Output will consist ofknumbers consisting of yourkscores, each score on a line by itself and right justified in a field 5 characters wide.
Sample input
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Sample output
260
一道典型的变异八皇后问题,每个节点带权值了。
#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
int arry[10][10],vis[3][20];
int maxnum;
void dfs(int pos,int num)
{
int i,j;
if(pos==8)
{
if(num>maxnum)
{
maxnum=num;
}
return;
}
else
{
for(i=0;i<8;i++)
{
if(!vis[0][i]&&!vis[1][i+pos]&&!vis[2][pos-i+8])
{
vis[0][i]=vis[1][i+pos]=vis[2][pos-i+8]=1;
dfs(pos+1,num+arry[pos][i]);
vis[0][i]=vis[1][i+pos]=vis[2][pos-i+8]=0;
}
}
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
int i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
cin>>arry[i][j];
}
}
memset(vis,0,sizeof(vis));
maxnum=0;
dfs(0,0);
cout<<setw(5)<<maxnum<<endl;
}
return 0;
}
分享到:
相关推荐
资源分类:Python库 所属语言:Python 资源全名:sultan-0.3.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Sultan POS的主要目标是小型市场,并且能够在Raspberry Pi上运行。特征联网(使用websocket) 多价项目类别供应商多用户和权限数据库SQLite / MySQL 销售报告物品销售报告资金报告使用平均值计算保证金客户资料库...
sultan-kernel-celox:适用于Samsung Skyrocket(SGH-I727)和Samsung Hercules(SGH-T989)的AOSP内核,基于官方的Samsung Jelly Bean内核源代码发布,并重新基于CAF jb_1.9.6
SULTAN-4TH-JUNE
资源分类:Python库 所属语言:Python 资源全名:sultan-0.3.1-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
餐厅项目 Sultan是使用Bootstrap构建的动态,适合移动设备的Web应用程序。 用户可以检查菜单并在线订购希腊食品。 灵感来自我梦想有一天开设自己的餐厅。
SpringPetClinic样品申请 通过一些图表了解Spring Petclinic应用程序 在本地运行诊所 Petclinic是使用构建的应用程序。 您可以构建一个jar文件并从命令行运行它: ...cd spring-petclinic ./mvnw package ...
苏丹-后-办公室-html-模板
Good hand written notes of our Prof.Ahmed Sultan about Discrete Fourier Transform
德维乔托莫 1、莫哈末阿齐兹·阿卜杜勒·拉赫曼 1、莫哈末哈达·穆罕默德·阿里夫 1、海里·扎姆祖里 2 和万·穆赫德·哈菲兹·万·阿兹里 2马来西亚工艺大学先进车辆系统研究小组,54100 Jalan Sultan Yahya Petra...
人口由马来西亚霹雳州SMK Sultan Tajul Ariffin Manong的中一至中二学生组成。 研究的设计是使用调查方法完成的。 对这些学生进行了问卷调查,以评估他们对YouTube在英语学习和自主学习中的使用的看法。 SPSS用于...
杰里科(Wadi Al-Qalt,Ain或Tal Sultan和Al-Nwehmeh)和拉马拉(Safa,Turmus Aya和Qibia)。 由于没有对这些地区进行分类研究,因此我们对巴勒斯坦的400个采样菌群进行了统计处理。 此外,分类是根据1979年的...
Sultan等人:监督机器学习算法的决策功能作为加速分子模拟的集体变量,arXiv预印本 使用以下图片可以概括总体思路: 给定开始状态和结束状态中的一些采样,SML算法(例如支持向量机)可以找到一个最大平面,该...
马来西亚霹雳州Pendidikan Sultan Idris Universiti Pendidikan Sultan Idris的Aplikasi Chrome Tab untuk staf dan pelajar。 马来西亚霹雳州Pendidikan Sultan Idris的Aplikasi Chrome Tab untuk kegunaan staf ...
合并 2020 年 3 月安全补丁 (9.0.0 最终版) 包含所有先前更新 合并 2020 年 1 月安全补丁 (9.0.0) 包含所有先前更新 合并 9 月安全补丁 (9.0.0_r48) 添加 4K 相机 (Sultan Hal) 改进相机快照索尼相机补丁 新的和改进...
Aljamaan、Sultan Eid、Ahmed Husseini Orabi、Mahmoud Husseini Orabi、Vahdat Abdelzad、Opeyemi Adesina、Aliaa Alghamdi、Aliaa Alghamdi Zakariapour,“Umple:面向开源和教育的模型驱动开发”,计算机编程科
我们的堆栈技术:JavaFX + OracleSQL数据集我们已经浏览了100个数据集,并选择了Nur-sultan(Astana)的房价,因为首先它是关于我们的国家的信息,并且它是一个非常有用的数据集,包含许多有用的列。 表结构: id...
因此,经过数小时的梳理和研究,我遇到了“ Sultan Badri”方法,该方法使用innerHTML在函数中创建项目。 这种方法对我来说自然而然,因为它使我能够在每页上创建一个基本的函数,并导出到索引。 我学到的是 如何...
历史25/05/2004 - Khalil Sultan (khalilsultan@msn.com) 的原创作品15/06/2004 - 代码修改。 08/07/2004 - 在 MATLAB Central 上重新修改和上传代码 - 文件交换。 与脚本的示例交互: *-*-*-*