链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=112&page=show_problem&problem=2159
类型: 暴力回溯
原题:
One song is extremely popular recently, so you and your friends decided to sing it in KTV. The song has 3 characters, so exactly 3 people should sing together each time (yes, there are 3 microphones in
the room). There are exactly 9 people, so you decided that each person sings exactly once. In other words, all the people are divided into 3 disjoint groups, so that every person is in exactly one group.
However, some people don't want to sing with some other people, and some combinations perform worse than others combinations. Given a score for every possible combination of 3 people, what is the largest
possible score for all the 3 groups?
Input
The input consists of at most 1000 test cases. Each case begins with a line containing a single integern(0
<n< 81), the number of possible combinations. The nextnlines
each contains 4 positive integersa,b,c,s(1
<=a<b<c<=
9, 0 <s< 10000), that means a score ofsis
given to the combination (a,b,c).
The last case is followed by a single zero, which should not be processed.
Output
For each test case, print the case number and the largest score. If it is impossible, print -1.
Sample Input
3
1 2 3 1
4 5 6 2
7 8 9 3
4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
0
Output for the Sample Input
Case 1: 6
Case 2: -1
题目大意:
有9个人去KTV唱歌, 然后要分组一起唱歌,每组3人,一人只能分在一个组里。 然而不同的组合效果不同, 而且某些人不想跟某些人同一组。 所以不同的组合的得分是不同的。求出这些组合中最高能得到的总分是多少。
分析与总结:
这题是Rujia
Liu's Problems for Beginners专题的第一题, 也是里面最简单的一题。
只需要暴力的回溯枚举出符合条件的情况,取其中最高的分数及可。
/*
* UVa 11218 - KTV
* 回溯
* Time: 0.312s (UVa)
* Author: D_Double
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int group[82][4], ans, n;
bool vis[82], occur[10];
void search(int cur,int tot){
if(cur >= 3){
if(tot > ans) ans = tot;
return;
}
for(int i=0; i<n; ++i)if(!vis[i]){
if(occur[group[i][0]] || occur[group[i][1]] || occur[group[i][2]])
continue;
occur[group[i][0]] = occur[group[i][1]] = occur[group[i][2]] = true;
vis[i] = true;
search(cur+1, tot+group[i][3]);
occur[group[i][0]] = occur[group[i][1]] = occur[group[i][2]] = false;
vis[i] = false;
}
}
int main(){
int cas=1;
while(scanf("%d", &n), n){
for(int i=0; i<n; ++i)
scanf("%d%d%d%d",&group[i][0],&group[i][1],&group[i][2],&group[i][3]);
ans = -1;
memset(vis, 0, sizeof(vis));
memset(occur, 0, sizeof(occur));
search(0, 0);
printf("Case %d: %d\n", cas++, ans);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
2014年湖南省第十届程序设计竞赛题目数据标程(by Rujia Liu) HNCPC 2014
UVa1318/LA2797 Monster Trap 《训练指南》代码仓库上Rujia Liu的源代码
所有代码均通过了UVa/La的测试,但不能保证程序是正确的(比如数据可能不够强),有疑问请致信rujia.liu@gmail.com,或在googlecode中提出: http://code.google.com/p/aoapc-book/ [最新更新] 2013-04-23 增加...
所有代码均通过了UVa/La的测试,但不能保证程序是正确的(比如数据可能不够强),有疑问请致信rujia.liu@gmail.com,或在googlecode中提出: http://code.google.com/p/aoapc-book/ [最新更新] 2013-04-23 增加...
作业提交:rujia.liu@gmail.com, liurj@mails.tsinghua.edu.cn 本次作业主要为算法讨论。注意:所有表格的各列都是:题号、题目名称、题目大意(如果教练没有填写或者觉得写得不够详细则请大家写算法时请补充完整)...
自述 此自述文件通常会记录启动和运行应用程序所需的任何步骤。 您可能想要涵盖的内容: Ruby版 系统依赖 配置 数据库创建 数据库初始化 如何运行测试套件 服务(作业队列、缓存服务器、搜索引擎等) ...
这是Su Jiya,Feng Zhang,Weifeng Liu,Bingsheng He,Ruuoan Wu,Du Xiaoyong Du,Wang Rujia Wang于2020年发表的题为“ CapelliniSpTRSV:GPU上无线程级同步的稀疏三角求解”的论文的源代码。 有两个版本,即...
只有如家酒店单品牌预订功能,代码更简练,维护更容易,更适用于地方站长用于做品牌类酒店预订的站长们,占用空间不到100M,也就是说只要你有空间,支持asp和access,那么你就可以拥有一个品牌类酒店预订的网站。...
| 我的帐户</a> | 酒店预订</a> | 会员俱乐部</a> | 目的地资讯</a> | 关于我们</a> | 联络我们</a> | 人才招聘</a></div>版权所有©2013 Rujia Co.,Ltd All Rights Reserved.如家快捷酒店(哈尔滨)有限公司 &...