hdu 3720 Arranging Your Team 夜

http://acm.hdu.edu.cn/showproblem.php?pid=3720

水题

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include <iomanip>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=30;
struct node
{
    int k,id;
    char name[50];
}mem[N];
int value[N][N];
bool had[N];
int ans;
int which(char stmp[])
{
    for(int i=1;i<=23;++i)
    if(strcmp(stmp,mem[i].name)==0)
    return i;
}
void dfs(int x,int keep,int def,int mid,int st)
{
    if(x==24)
    {
        if(!(keep==1&&def==4&&mid==4&&st==2))
        return ;
        int num=0;
        for(int i=1;i<=23;++i)
        {
            if(had[i])
            {
                num+=mem[i].k;
                for(int j=i+1;j<=23;++j)
                {
                    if(had[j])
                    {
                        num+=value[i][j];
                    }
                }
            }
        }
        if(num>ans)
        ans=num;
        return ;
    }
    dfs(x+1,keep,def,mid,st);
    bool in=false;
    if(mem[x].id==1&&keep<1)
    {++keep;in=true;}
    if(mem[x].id==2&&def<4)
    {++def;in=true;}
    if(mem[x].id==3&&mid<4)
    {++mid;in=true;}
    if(mem[x].id==4&&st<2)
    {++st;in=true;}
    if(in)
    {
        had[x]=true;
        dfs(x+1,keep,def,mid,st);
        had[x]=false;
    }
}
int F(char stmp[])
{
    if(strcmp(stmp,"goalkeeper")==0)
    return 1;
    if(strcmp(stmp,"defender")==0)
    return 2;
    if(strcmp(stmp,"midfielder")==0)
    return 3;
    return 4;
}
int main()
{
    freopen("data.txt","r",stdin);
    char stmp[50];
    while(scanf("%s %d %s",mem[1].name,&mem[1].k,stmp)!=EOF)
    {
       mem[1].id=F(stmp);
       for(int i=2;i<=23;++i)
       {
           scanf("%s %d %s",mem[i].name,&mem[i].k,stmp);
           mem[i].id=F(stmp);
       }
       memset(value,0,sizeof(value));
       int m;
       cin>>m;
       while(m--)
       {
           char stmp1[50],stmp2[50];
           int v;
           scanf("%s %s %d",stmp1,stmp2,&v);
           int i=which(stmp1);
           int j=which(stmp2);
           value[i][j]=value[j][i]=v;
       }
       memset(had,false,sizeof(had));
       ans=-INF;
       dfs(1,0,0,0,0);
       if(ans==-INF)
       printf("impossible\n");
       else
       printf("%d\n",ans);
    }
    return 0;
}