首页 > 搜索 > DFS搜索 > HDU 3720-Arranging Your Team-DFS-[解题报告]HOJ
2015
02-21

HDU 3720-Arranging Your Team-DFS-[解题报告]HOJ

Arranging Your Team

问题描述 :

Your country has qualified for the FIFA 2010 South Africa World Cup. As the coach, you have made up the 23 men squad. Now you must select 11 of them as the starters. As is well known, there are four positions in soccer: goalkeeper, defender, midfielder and striker. Your favorite formation is 4-4-2, that is, you should choose 4 defenders, 4 midfielders, 2 strikers, and of course, 1 goalkeeper. As a retired ACMer, you want to write a program to help you make decision. Each person’s ability has been evaluated as a positive integer. And what’s more, for some special pairs of persons, if the two people are both on the field, there will be an additional effect (positive or negative). Now you should choose the 11 persons to make the total value maximum.

输入:

There are multiple test cases, separated by an empty line. The first 23 lines of each test case indicate each person’s name Si, ability value Vi, and position. The length of each name is no more than 30, and there are no whitespaces in the names. All the names are different. The ability values are positive integers and no more than 100. The position is one of "goalkeeper", "defender", "midfielder" and "striker".

Then an integer M indicates that there are M special pairs. Each of the following M lines contains Si, Sj and Cij, means that if Si and Sj are both on the field, the additional profit is Cij. (-100 ≤ Cij ≤ 100). Si and Sj are different strings, and must be in the previous 23 names. All the (Si, Sj) pairs
are different.

输出:

There are multiple test cases, separated by an empty line. The first 23 lines of each test case indicate each person’s name Si, ability value Vi, and position. The length of each name is no more than 30, and there are no whitespaces in the names. All the names are different. The ability values are positive integers and no more than 100. The position is one of "goalkeeper", "defender", "midfielder" and "striker".

Then an integer M indicates that there are M special pairs. Each of the following M lines contains Si, Sj and Cij, means that if Si and Sj are both on the field, the additional profit is Cij. (-100 ≤ Cij ≤ 100). Si and Sj are different strings, and must be in the previous 23 names. All the (Si, Sj) pairs
are different.

样例输入:

Buffon 90 goalkeeper
De_Sanctis 80 goalkeeper
Marchetti 80 goalkeeper
Zambrotta 90 defender
Cannavaro 90 defender
Chiellini 90 defender
Maggio 90 defender
Bonucci 80 defender
Criscito 80 defender
Bocchetti 80 defender
Pirlo 90 midfielder
Gattuso 90 midfielder
De_Rossi 90 midfielder
Montolivo 90 midfielder
Camoranesi 80 midfielder
Palombo 80 midfielder
Marchisio 80 midfielder
Pepe 80 midfielder
Iaquinta 90 striker
Di_Natale 90 striker
Gilardino 80 striker
Quagliarella 80 striker
Pazzini 80 striker
1
Pirlo Quagliarella 50

ZhangSan01 50 goalkeeper
ZhangSan02 50 defender
ZhangSan03 50 defender
ZhangSan04 50 defender
ZhangSan05 50 defender
ZhangSan06 50 defender
ZhangSan07 50 defender
ZhangSan08 50 defender
ZhangSan09 50 defender
ZhangSan10 50 defender
ZhangSan11 50 defender
ZhangSan12 50 defender
ZhangSan13 50 defender
ZhangSan14 50 defender
ZhangSan15 50 defender
ZhangSan16 50 midfielder
ZhangSan17 50 midfielder
ZhangSan18 50 midfielder
ZhangSan19 50 midfielder
ZhangSan20 50 midfielder
ZhangSan21 50 midfielder
ZhangSan22 50 midfielder
ZhangSan23 50 midfielder
0

样例输出:

1030
impossible

不可能解可以直接判断。

搭配产生的附加分可以用一个二维数组保存。

枚举1442,4种类型的人,因为总人数只有23个,所以可以搜索暴力枚举,然后保存最优解。

注意trick,答案可能为负数,所以初始化ans不能为0.

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define maxn 1005
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
using namespace std;

typedef long long ll;
char name[100];
char type[100];
int power[30];
int maps[30][30];
map<string,int> mt;
map<string,int> na;
int mp[30];
vector<int> player[4];
vector<int> ans;
int ANS;
void dfs2(int pos,int sum);
void dfs3(int pos,int sum);
void dfs4(int pos,int sum);

void dfs1(int pos,int sum)
{
    if(sum==1) {dfs2(-1,0);return;}
    for(int i=pos+1;i<player[0].size();i++)
    {
        ans.push_back(player[0][i]);
        dfs1(i,sum+1);
        ans.pop_back();
    }
}
void dfs2(int pos,int sum)
{
    if(sum==4) {dfs3(-1,0);return;}
    for(int i=pos+1;i<player[1].size();i++)
    {
        ans.push_back(player[1][i]);
        dfs2(i,sum+1);
        ans.pop_back();
    }
}
void dfs3(int pos,int sum)
{
    if(sum==4) {dfs4(-1,0);return;}
    for(int i=pos+1;i<player[2].size();i++)
    {
        ans.push_back(player[2][i]);
        dfs3(i,sum+1);
        ans.pop_back();
    }
}
void dfs4(int pos,int sum)
{
    if(sum==2)
    {
        int s=0;
        for(int i=0;i<ans.size();i++)
        {
            for(int j=i+1;j<ans.size();j++)
            {
                s+=maps[ans[i]][ans[j]];
            }
            s+=power[ans[i]];
        }
        ANS=max(s,ANS);
        return;
    }
    for(int i=pos+1;i<player[3].size();i++)
    {
        ans.push_back(player[3][i]);
        dfs4(i,sum+1);
        ans.pop_back();
    }
}
int main()
{
    mt["goalkeeper"]=0;
    mt["defender"]=1;
    mt["midfielder"]=2;
    mt["striker"]=3;
    int p;
    while(cin>>name)
    {
        ANS=-0x3f3f3f3f;
        ans.clear();
        na.clear();
        for(int i=0;i<4;i++) player[i].clear();

        cin>>p>>type;
        player[mt[type]].push_back(1);
        power[1]=p;

        na[name]=1;
        for(int i=2;i<=23;i++)
        {
            cin>>name>>p>>type;
            na[name]=i;
            player[mt[type]].push_back(i);
            power[i]=p;
        }
        int n;
        memset(maps,0,sizeof(maps));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>name>>type>>p;
            maps[na[name]][na[type]]=p;
            maps[na[type]][na[name]]=p;
        }

        if(player[0].size()<1||player[1].size()<4||player[2].size()<4||player[3].size()<2)
        {
            cout<<"impossible"<<endl;
            continue;
        }
        dfs1(-1,0);
        cout<<ANS<<endl;
    }
    return 0;
}

 

 

参考:http://www.cnblogs.com/suncoolcat/archive/2013/10/08/3358115.html


,
  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测