椅子"/>
神奇的椅子
题目较长,直接上图
思路:暴力枚举,也就是深度搜索,搜索出所有可能的组合,然和计算该组合的分数:
首先是深度搜索进行枚举
假设我们男人,女人,孩子的人数分别为1,1,1 。我们就安排三个座位,第一个座位可以安排男人,女人,或者孩子,后面两个座位类似安排,这就是枚举,同时注意一些条件,比如男人不能坐在孩子前面,枚举时注意去掉这些,这就是剪枝。
#include <iostream>
#include <string>
using namespace std;
string ans;//用来存储每个位置放入的人,下标相当于座位号,我们从1号座位开始安排
//可以把ans改为sit便于理解
int m,w,c,total;//分别表示男人,女人,孩子和总人数
void display() {//打印ans,我们从下标1开始安排,所以从下标1开始打印for (int i = 1; i <total; i++) {cout << ans[i] << "->";}cout << ans[total];cout << endl;
}
void dfs(int index,int m,int w,int c) {//深度优先搜索,参数依次为,安排第index位置,后面依次为剩余男人,女人,小孩的人数if (index==total+1) {//边界条件,也就是所有人数都安置完了display();return;}if (c > 0 && ans[index - 1] != 'M') {//这里有个剪枝:当前面一个位置是男人时,后面不允许是小孩ans.push_back('C');//放置小孩dfs(index + 1, m, w, c - 1);//进入下一步搜索,索搜index+1位置,同时孩子的人数-1ans.pop_back();//回溯}if (w > 0 ) {ans.push_back('W');//放置女人dfs(index + 1, m, w - 1, c);ans.pop_back();}if (m > 0) {ans.push_back('M');//放置男人dfs(index + 1, m - 1, w, c);ans.pop_back();}
}
int main() {while (cin >> m >> w >> c) {total = m + w + c;ans.clear();ans.push_back('0');//我们从下标1开始放置,所以在下标0处随便填充一个字符dfs(1, m, w, c);//从1处开始搜索}
}
运行结果:
1 1 1
C->W->M
C->M->W
W->C->M
M->W->C
可以看到,我们枚举出4种所有的可能,仔细一看,还是有些问题,第一种是不允许的,因为我们用的是一个线性结构,而题目是一个环形,最后一个男人相当于坐在了第一个男人前面。我们在后面计分的时候把这种情况记为0分就行 。
如何计分呢,很简单,遍历搜索就完事了,先搜有没有家庭组合,再搜有没有父子组合,然后母子组合,注意:家庭组合包含了母子组合,最后搜有没有扣分的情况。
double grade(const string &s) {double sum = m * 2 + w * 1 + c*0.5;int n1 = 0, n2 = 0; //n1表示家庭组合数,n2表示母子组合数if (s[1] == 'C'&& s[total] == 'M')//前面说过这种情况,记为0分return 0;else {//搜索家庭组合for (int i = 1; i <= total - 2; i++) {if (s[i] == 'C'&&s[i + 1] == 'W'&&s[i + 2] == 'M') {sum += 3;n1++;}}//注意题目是环形,所以我们还要搜索下面两种,后面的情况类似处理if (s[total - 1] == 'C'&&s[total] == 'W'&&s[1] == 'M') {sum += 3;n1++;}if (s[total] == 'C'&&s[1] == 'W'&&s[2] == 'M') {sum += 3;n1++;}//搜索父子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'M')sum += 2.5;if (s[total] == 'C'&&s[1] == 'M')sum += 2.5;//索搜母子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'W')n2++;if (s[total] == 'C'&&s[1] == 'W')n2++;sum += (n2 - n1) * 2;//家庭组合包含了母子组合,不能重复计分//搜索扣分的情况for (int i = 1; i <= total - 1; i++)if (s[i] == 'M'&&s[i + 1] == 'W')sum--;if (s[total] == 'M'&&s[1] == 'W')sum--;}return sum;//返回
}
然后把上面两个整合下;
#include <iostream>
#include <string>
using namespace std;
string ans;//用来存储每个位置放入的人
int m, w, c, total;//分别表示男人,女人,孩子和总人数
void display() {//打印ans,我们从下标1开始存,所以从下标1开始打印for (int i = 1; i <total; i++) {cout << ans[i] << "->";}cout << ans[total];cout << endl;
}
double grade(const string &s) {double sum = m * 2 + w * 1 + c*0.5;int n1 = 0, n2 = 0; //n1表示家庭组合数,n2表示母子组合数if (s[1] == 'C'&& s[total] == 'M')//前面说过这种情况,记为0分return 0;else {//搜索家庭组合for (int i = 1; i <= total - 2; i++) {if (s[i] == 'C'&&s[i + 1] == 'W'&&s[i + 2] == 'M') {sum += 3;n1++;}}//注意题目是环形,所以我们还要搜索下面两种,后面的情况类似处理if (s[total - 1] == 'C'&&s[total] == 'W'&&s[1] == 'M') {sum += 3;n1++;}if (s[total] == 'C'&&s[1] == 'W'&&s[2] == 'M') {sum += 3;n1++;}//搜索父子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'M')sum += 2.5;if (s[total] == 'C'&&s[1] == 'M')sum += 2.5;//索搜母子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'W')n2++;if (s[total] == 'C'&&s[1] == 'W')n2++;sum += (n2 - n1) * 2;//家庭组合包含了母子组合,不能重复计分//搜索扣分的情况for (int i = 1; i <= total - 1; i++)if (s[i] == 'M'&&s[i + 1] == 'W')sum--;if (s[total] == 'M'&&s[1] == 'W')sum--;}return sum;//返回
}
void dfs(int index, int m, int w, int c) {//深度优先搜索,参数依次为,安排第index位置,后面依次为剩余男人,女人,小孩的人数if (index == total + 1) {//边界条件,也就是所有人数都安置完了display();cout << "该组合的分数为:" << grade(ans) << endl;return;}if (c > 0 && ans[index - 1] != 'M') {//这里有个剪枝:当前面一个位置是男人时,后面不允许是小孩ans.push_back('C');//放置小孩dfs(index + 1, m, w, c - 1);//进入下一步搜索,索搜index+1位置,同时孩子的人数-1ans.pop_back();//回溯}if (w > 0) {ans.push_back('W');//放置女人dfs(index + 1, m, w - 1, c);ans.pop_back();}if (m > 0) {ans.push_back('M');//放置男人dfs(index + 1, m - 1, w, c);ans.pop_back();}
}
int main() {while (cin >> m >> w >> c) {total = m + w + c;ans.clear();ans.push_back('0');//我们从下标1开始放置,所以在下标0处随便填充一个字符dfs(1, m, w, c);//从1处开始搜索}
}
运行结果:
0 1 1
C->W
该组合的分数为:3.5
W->C
该组合的分数为:3.5
1 0 1
C->M
该组合的分数为:0
1 1 1
C->W->M
该组合的分数为:0
C->M->W
该组合的分数为:5
W->C->M
该组合的分数为:5
M->W->C
该组合的分数为:5
最后整理为题目的答案:
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
string ans;//用来存储每个位置放入的人
int m, w, c, total;//分别表示男人,女人,孩子和总人数
double score;//保存分数
void display() {//打印ans,我们从下标1开始存,所以从下标1开始打印for (int i = 1; i <total; i++) {cout << ans[i] << "->";}cout << ans[total];cout << endl;
}
double grade(const string &s) {double sum = m * 2 + w * 1 + c*0.5;int n1 = 0, n2 = 0; //n1表示家庭组合数,n2表示母子组合数if (s[1] == 'C'&& s[total] == 'M')//前面说过这种情况,记为0分return 0;else {//搜索家庭组合for (int i = 1; i <= total - 2; i++) {if (s[i] == 'C'&&s[i + 1] == 'W'&&s[i + 2] == 'M') {sum += 3;n1++;}}//注意题目是环形,所以我们搜索下面两种,后面的情况类似处理if (s[total - 1] == 'C'&&s[total] == 'W'&&s[1] == 'M') {sum += 3;n1++;}if (s[total] == 'C'&&s[1] == 'W'&&s[2] == 'M') {sum += 3;n1++;}//搜索父子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'M')sum += 2.5;if (s[total] == 'C'&&s[1] == 'M')sum += 2.5;//索搜母子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'W')n2++;if (s[total] == 'C'&&s[1] == 'W')n2++;sum += (n2 - n1) * 2;//家庭组合包含了母子组合,不能重复计分//搜索扣分的情况for (int i = 1; i <= total - 1; i++)if (s[i] == 'M'&&s[i + 1] == 'W')sum--;if (s[total] == 'M'&&s[1] == 'W')sum--;}return sum;//返回
}
void dfs(int index, int m, int w, int c) {//深度优先搜索,参数依次为,安排第index位置,后面依次为剩余男人,女人,小孩的人数if (index == total + 1) {//边界条件,也就是所有人数都安置完了score = max(score, grade(ans));return;}if (c > 0 && ans[index - 1] != 'M') {//这里有个剪枝:当前面一个位置是男人时,后面不允许是小孩ans.push_back('C');//放置小孩dfs(index + 1, m, w, c - 1);//进入下一步搜索,索搜index+1位置,同时孩子的人数-1ans.pop_back();//回溯}if (w > 0) {ans.push_back('W');//放置女人dfs(index + 1, m, w - 1, c);ans.pop_back();}if (m > 0) {ans.push_back('M');//放置男人dfs(index + 1, m - 1, w, c);ans.pop_back();}
}
int main() {while (cin >> m >> w >> c) {total = m + w + c;ans.clear();//初始化score = 0;//初始化ans.push_back('0');//我们从下标1开始放置,所以在下标0处随便填充一个字符dfs(1, m, w, c);//从1处开始搜索cout << fixed << setprecision(1) << score << endl;}
}
运行结果:
1 1 1
5.0
3 2 1
10.5
更多推荐
神奇的椅子
发布评论