Arranging Your Team HDU - 3720 【DFS】

思路

题意：此题大意是指首先给你23个队员的信息，包括他们的名字，能力值，在赛场上的职位。然后给出几个若能满足某两个队员同时在球场上就额外加上一定的值。最后让你从23个队员中选出11个人，使得最终的value最大。

具体思路：由于从样例中可以发现字符串比较多，加之需要进行姓名和姓名、score之间关系的记录，这就用到了map。利用dfs对所有队员进行遍历，具体说明在代码中指出。

AC代码

//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<algorithm>

using namespace std;

map<string, int> id;

map<string, int> manid;

int def = 4, mid = 4, str = 2, goal = 1;

int sum[6], M, asso[24][24];

int vis[24];

int maxs = 0;

struct Men

{

    int value, pos;

};

Men man[24];

void init()

{

    string s = "defender";

    id[s] = 1;

    s = "midfielder";

    id[s] = 2;

    s = "striker";

    id[s] = 3;

    s = "goalkeeper";

    id[s] = 4;

}

void dfs(int last, int d, int m, int s, int g) 		//d, m, s, g分别指defenders, midfielders,  strikers, goalkeeper，last可以避免重复

{

    if(d == 4 && m == 4 && s == 2 && g == 1)		//满足条件时

    {

        int cnt = 0;

        for(int i = 0; i < 23; i++)

        {

            if(vis[i])

            {

                cnt += man[i].value;

                for(int j = i + 1; j < 23; j++)

                {

                    if(vis[j])

                    {

                        cnt += asso[i+1][j+1];

                    }

                }

            }

        }

        maxs = max(maxs, cnt);			//不断记录所有情况，最后得到最大值

        return ;

    }

    for(int i = last; i < 23; i++)

    {

        if(vis[i])

            continue;

        if(man[i].pos == 1 && d >= 4) continue;

        if(man[i].pos == 2 && m >= 4) continue;

        if(man[i].pos == 3 && s >= 2) continue;

        if(man[i].pos == 4 && g >= 1) continue;

        vis[i] = 1;

        if(man[i].pos == 1)

            dfs(i, d+1, m, s, g);

        else if(man[i].pos == 2)

            dfs(i, d, m+1, s, g);

        else if(man[i].pos == 3)

            dfs(i, d, m, s+1, g);

        else if(man[i].pos == 4)

            dfs(i, d, m, s, g+1);

        vis[i] = 0;

    }

}

int main()

{

    // freopen("input.txt", "r", stdin);

    // freopen("output.txt", "w", stdout);

    init();

    string na, p;

    int v;

    while(cin >> na )

    {

        cin >> v >> p;

        manid.clear();

        man[0].value = v;

        manid[na] = 1;

        man[0].pos = id[p];

        memset(sum, 0, sizeof(sum));

        sum[id[p]] ++;

        for(int i = 1; i < 23; i++)

        {

            cin >> na >> v >> p;

            manid[na] = i + 1;

            man[i].value = v;

            man[i].pos = id[p];

            sum[id[p]] ++;

        }

        cin >> M;

        memset(asso, 0, sizeof(asso));

        for(int i = 0; i < M; i++)

        {

            string s1, s2;

            int s;

            cin >> s1 >> s2 >> s;

            asso[manid[s1]][manid[s2]] = s;		//记录s1, s2同时存在时的score值

            asso[manid[s2]][manid[s1]] = s;

        }

        if(sum[1] < 4 || sum[2] < 4 || sum[3] < 2 || sum[4] < 1)

        {

            cout << "impossible" << endl;

            continue;

        }

        memset(vis, 0, sizeof(vis));

        maxs = -0x7ffffff;

        dfs(0, 0, 0, 0, 0);

        cout << maxs << endl;

    }

}