先分组,然后暴力;注意 初始化时不要为0 会有负数;我直接二进制枚举; dfs是正解;呵呵
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <algorithm> using namespace std; int arr[25][25]; map<string,int>mp; char str[1000],cha[1000]; struct date{ int val,i; bool operator < ( const date &a )const { if( a.val != val )return a.val < val; return a.i < i; } }; vector<date>v[6]; vector<date>s[6]; char sss[5][55] = {"0","goalkeeper","defender","midfielder","striker"}; int main( ) { int num; while( scanf("%s%d%s",str,&num,cha) != EOF ) { mp.clear(); memset( arr,0,sizeof(arr) ); for( int i = 0; i < 6; i++ )v[i].clear(); for( int i = 0; i < 6; i++ )s[i].clear(); mp[str] = 1; date temp; temp.val = num; temp.i = 1; for( int i = 1; i <= 4; i++ ) if( strcmp(cha,sss[i]) == 0 ) v[i].push_back(temp); for( int i = 2; i <= 23; i++ ) { scanf("%s%d%s",str,&num,cha); mp[str] = i; date temp; temp.val = num; temp.i = i; for( int j = 1; j <= 4; j++ ) if( strcmp(cha,sss[j]) == 0 )v[j].push_back(temp); } int now; cin>>now; while( now-- ) { cin>>str>>cha>>num; arr[mp[str]][mp[cha]] = arr[mp[cha]][mp[str]] = num; }//cout<<v[1].size()<<" "<<v[2].size()<<" "<<v[3].size()<<" "<<v[4].size()<<endl; if( v[1].size() < 1 || v[2].size() < 4 || v[3].size() < 4 || v[4].size() < 2 ) { cout<<"impossible"<<endl; continue; } for( int i = 0; i < v[1].size(); i++ ) { date temp; temp = v[1][i]; temp.i = 1<<(temp.i-1); s[1].push_back( temp ); } for( int i = 0; i < v[2].size(); i++ ) for( int j = i+1; j < v[2].size(); j++ ) for( int k = j+1; k < v[2].size(); k++ ) for( int l = k+1; l < v[2].size(); l++ ) { int ans = 0; int val = 0; date temp; temp = v[2][i]; ans += (1<<(temp.i-1));val += temp.val; temp = v[2][j]; ans += (1<<(temp.i-1));val += temp.val; temp = v[2][k]; ans += (1<<(temp.i-1));val += temp.val; temp = v[2][l]; ans += (1<<(temp.i-1));val += temp.val; temp.val = val; temp.i = ans; s[2].push_back(temp); } for( int i = 0; i < v[3].size(); i++ ) for( int j = i+1; j < v[3].size(); j++ ) for( int k = j+1; k < v[3].size(); k++ ) for( int l = k+1; l < v[3].size(); l++ ) { int ans = 0; int val = 0; date temp; temp = v[3][i]; ans += (1<<(temp.i-1));val += temp.val; temp = v[3][j]; ans += (1<<(temp.i-1));val += temp.val; temp = v[3][k]; ans += (1<<(temp.i-1));val += temp.val; temp = v[3][l]; ans += (1<<(temp.i-1));val += temp.val; temp.val = val; temp.i = ans; s[3].push_back(temp); } for( int i = 0; i < v[4].size(); i++ ) for( int j = i+1; j < v[4].size(); j++ ) { int ans = 0; int val = 0; date temp; temp = v[4][i]; ans += (1<<(temp.i-1));val += temp.val; temp = v[4][j]; ans += (1<<(temp.i-1));val += temp.val; temp.val = val; temp.i = ans; s[4].push_back(temp); } int Max = (1<<30)*-1; for( int i = 0; i < s[1].size(); i++ ) for( int j = 0; j < s[2].size(); j++ ) for( int k = 0; k < s[3].size(); k++ ) for( int l = 0; l < s[4].size(); l++ ) { int ans = s[1][i].i+s[2][j].i+s[3][k].i+s[4][l].i; int val = s[1][i].val+s[2][j].val+s[3][k].val+s[4][l].val; vector<int>n; n.clear(); for( int t = 0; t < 24; t++ ) if( ans&(1<<t) )n.push_back(t+1); for( int x = 0; x < n.size(); x++ ) for( int y = x+1; y < n.size(); y++ ) val += arr[n[x]][n[y]]; Max = max( Max,val ); } cout<<Max<<endl; } return 0; }