HDU 3720 深搜 枚举
2024-09-14 16:27:23
DES:从23个队员中选出4—4—2—1共4种11人来组成比赛队伍。给出每个人对每个职位的能力值。给出m组人在一起时会产生的附加效果。问你整场比赛人员的能力和最高是多少。
用深搜暴力枚举每种类型的人选择情况。感觉是这个深搜写的很机智。
在vector中存结构体就会很慢。TLE。直接存序号就AC了。以后还是尽量少用结构体吧。
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<iostream>
using namespace std; vector<int>play[];
vector<int>ans;
int pow[];
map<string, int>mtype;
map<string, int>mname;
int eff[][];
int maxn = ; void dfs2(int, int );
void dfs3(int, int );
void dfs4(int, int ); void dfs1(int pos, int sum)
{
if (sum == )
{
dfs2(-, );
return;
}
for (int i=pos+; i<play[].size(); ++i)
{
ans.push_back(play[][i]);
dfs1(i, sum+);
ans.pop_back();
}
} void dfs2(int pos, int sum)
{
if (sum == )
{
dfs3(-, );
return;
}
for (int i=pos+; i<play[].size(); ++i)
{
ans.push_back(play[][i]);
dfs2(i, sum+);
ans.pop_back();
}
} void dfs3(int pos, int sum)
{
if (sum == )
{
dfs4(-, );
return;
}
for (int i=pos+; i<play[].size(); ++i)
{
ans.push_back(play[][i]);
dfs3(i, sum+);
ans.pop_back();
}
} void dfs4(int pos, int sum)
{
if (sum == )
{
int anss = ;
for (int i=; i<ans.size(); ++i)
{
for (int j=i+; j<ans.size(); ++j)
{
anss += eff[ans[i]][ans[j]];
}
anss += pow[ans[i]];
}
if (anss > maxn)
maxn = anss;
return;
}
for (int i=pos+; i<play[].size(); ++i)
{
ans.push_back(play[][i]);
dfs4(i, sum+);
ans.pop_back();
}
} int main()
{
mtype["goalkeeper"] = ;
mtype["defender"] = ;
mtype["midfielder"] = ;
mtype["striker"] = ;
char name[], type[];
int power;
while(cin >> name)
{
maxn = -0x3f3f3f3f;
ans.clear();
for (int i=; i<; ++i) play[i].clear(); cin >> power >> type;
int tt = mtype[type];
pow[] = power;
mname[name] = ;
play[tt].push_back();
memset(eff, , sizeof(eff)); for (int i=; i<=; ++i)
{
cin >> name >> power >> type;
pow[i] = power;
mname[name] = i;
int tt = mtype[type];
play[tt].push_back(i);
} int n;
cin >> n;
int n1, n2, add;
char na1[], na2[];
for (int i=; i<=n; ++i)
{
cin >> na1 >> na2 >> add;
n1 = mname[na1];
n2 = mname[na2];
eff[n1][n2] = add;
eff[n2][n1] = add;
}
int a[] = {, , , };
bool flag = true;
for (int i=; i<; ++i)
{
if (play[i].size() < a[i])
{
flag = false;
break;
}
}
if (!flag)
{
cout << "impossible\n";
continue;
} dfs1(-, );
cout << maxn << endl;
}
return ;
}
LOoK
最新文章
- iOS可视化动态绘制八种排序过程
- PEtools
- css学习笔记(4)
- Eclipse的安装和java环境变量的设置
- JQ工具函数
- zt:如何快速赚取人生第一个100万?
- BigInteger
- 再探java基础——对面向对象的理解(2)
- altium designer 原理图复制出错
- leetcode add two numbers python
- openwrt 的 inittab
- 2015 HDU 计算机学院 院赛 1003 玩骰子
- MySQL 8 新特性之持久化全局变量的修改
- go语言学习--go中godep的使用小结
- c/c++ 整数除预算保留小数
- “Linux内核分析”第五周报告
- Java编程的逻辑 (82) - 理解ThreadLocal
- js数据类型和变量
- WebRTC 基于GCC的拥塞控制(下)
- win10下安装Jenkins
热门文章
- SQL语句 查询同一个字符在某一个字符串中出现的次数
- Python3基础 函数 递归 阶乘与斐波那契数列
- HDU 1823 Luck and Love (二维线段树&;区间最值)题解
- 圆点博士 陀螺仪和加速度计MPU6050的单位换算方法
- LookupError: Couldn&#39;t find path to unrar library.
- 用NotePad++如何实现大小写转换
- Spring AOP之使用注解创建切面
- 《剑指offer》第十题(斐波那契数列)
- Android TableLayout中的使用说明
- Codeforces 595D - Max and Bike