题解 P6248 【准备战斗，选择你的英雄】

lzqy_ · 2020-03-29 09:41:42 · 题解

一道暴力搜索题，但是个人感觉并没有其他大佬写的那么复杂

思路就很简单，用一个map来记录名字对应的编号，然后通过DFS枚举取六个英雄的所有可能性（不需要考虑别的，纯枚举）。不会DFS的点这里。

所以，我们用DFS实现从1~n个数字里选6个数字，且不考虑顺序（最简单、最基础的深搜）。

注意：

题目的坑点是英雄组合可以重复，记得考虑这一点。

具体实现方法看代码（有详细注释）：

#include <bits/stdc++.h>
using namespace std;
map<string,int>m;
int together[100][100],power[100],a[100]={1},ans,n,K;
//together[i][j]表示第i,j个英雄同时上阵增加的能力值；
//power[i]表示第i个英雄的个人能力值；
//a数组用来记录DFS枚举结果。
bool k[100];
void moni()
{
  int pmax=0;
  for(int i=1; i<=6; i++)
  {
    pmax+=power[a[i]];//加上英雄的个人能力值
    for(int j=1; j<=n; j++)//范围不大直接爆搜
      if(k[j])//如果另一个英雄也上阵了
        pmax+=together[a[i]][j];
  }
  ans=max(ans,pmax);//更新最大值
}
void dfs(int kk)//典型深搜
{
  if(kk==7||kk==n+1)//枚举完六个英雄或是n个英雄
    moni();
  else
    for(int i=a[kk-1]; i<=n; i++)
      if(!k[i])//如果第i个英雄没有上阵
      {
        k[i]=1;
        a[kk]=i;
        dfs(kk+1);
        k[i]=0;
      }
}
int main()
{
  string s,ss;
  cin>>n>>K;
  for(int i=1; i<=n; i++)
  {
    cin>>s>>power[i];
    m[s]=i;//名字s对应编号i
  }
  for(int i=0; i<K; i++)
  {
      cin>>s>>ss>>h;
      together[m[s]][m[ss]]+=h;
      //注：此处要用+=来进行叠加
  }
  dfs(1);//开始深搜
  cout<<ans;//输出结果
  return 0;
}

for新手（个人的建议）：

深搜的时候不用考虑那么多，只枚举简单的，至于后面的模拟，不要放在深搜里面执行，这样的思路会更清晰些。