首页 > 代码库 > HDU-4924-Football Manager(DFS+DP)
HDU-4924-Football Manager(DFS+DP)
Problem Description
Football Manager is a series of football management simulation games developed by Sports Interactive and published by Sega. In this game, you will play a role of a football club manager and conduct your team to chase championship titles. As a football team manager, you need to take responsibilities for tactics developing, training arrangements, on-pitch commanding, player trading, etc. One of the most important things is to select your starting line-up.
According to the rules of football matches, there should be 11 players in your starting line-up, where one of them must be a goalkeeper. Besides the goalkeeper (GK), there’re three classes of positions: defender (DF), midfielder (MF), and striker (ST).
When a manager is selecting his starting line-up, he usually determines the formation first. The football formation is usually noted like “4-4-2”“4-5-1”“4-3- 3”, etc. For example, the “4-5-1” formation denotes that there are 4 defenders, 5 midfielders and 1 striker. Note that every player has his preferred positions, and they will always refuse to appear at positions he does not prefer, while some excellent players may be qualified for several positions. For example, C. Ronaldo can play as both a striker and a midfielder.
In the game, players have two important attributes for each of his preferred positions: CA (current ability) and PA (potential ability). The CA of the line-up is defined as the sum of the 11 players’ CA in the formation. Similar to CA, the PA of the line-up equals to the sum of 11 players’ PA. Then your task is to select the proper players to reach maximum CA of your line-up. When a tie occurs, the one of maximum PA is required.
Beyond these requirements and limits, the relationships between players also make sense to the CA of your line-up. Every player may like or dislike some of his teammates. When he and the one he likes are both on the pitch, the CA of the line-up will be increased by a specific value. On the contrary, when someone and his disliked player occurs on the pitch concurrently, the line-up’s CA will be decreased. Be careful that the like and dislike relationships between players are unidirectional. Not surprisingly, Plane.Gao likes Messi very much while Messi may not know Plane.Gao at all.
According to the rules of football matches, there should be 11 players in your starting line-up, where one of them must be a goalkeeper. Besides the goalkeeper (GK), there’re three classes of positions: defender (DF), midfielder (MF), and striker (ST).
When a manager is selecting his starting line-up, he usually determines the formation first. The football formation is usually noted like “4-4-2”“4-5-1”“4-3- 3”, etc. For example, the “4-5-1” formation denotes that there are 4 defenders, 5 midfielders and 1 striker. Note that every player has his preferred positions, and they will always refuse to appear at positions he does not prefer, while some excellent players may be qualified for several positions. For example, C. Ronaldo can play as both a striker and a midfielder.
In the game, players have two important attributes for each of his preferred positions: CA (current ability) and PA (potential ability). The CA of the line-up is defined as the sum of the 11 players’ CA in the formation. Similar to CA, the PA of the line-up equals to the sum of 11 players’ PA. Then your task is to select the proper players to reach maximum CA of your line-up. When a tie occurs, the one of maximum PA is required.
Beyond these requirements and limits, the relationships between players also make sense to the CA of your line-up. Every player may like or dislike some of his teammates. When he and the one he likes are both on the pitch, the CA of the line-up will be increased by a specific value. On the contrary, when someone and his disliked player occurs on the pitch concurrently, the line-up’s CA will be decreased. Be careful that the like and dislike relationships between players are unidirectional. Not surprisingly, Plane.Gao likes Messi very much while Messi may not know Plane.Gao at all.
Input
The input contains multiple test cases. The first line of input gives the number of test cases T (1<=T<=20).
For each test case, the first line contains an integer N (1<=N<=20), the total number of players in your team.
Each of the following N lines describe a player in the following format:
<SquadNum> <PositionNum> <pos1> <CA1> <PA1> <pos2> <CA2> <PA2> . . . <posnum><CAnum><PAnum>
Here:
<SquadNum> denotes the player’s unique squad number (between 1 and 99, inclusive).
<PositionNum> denotes the number of positions he preferred.
<pos1> <pos2> . . . <posnum> are strings chosen in {GK, DF, MF, ST},denoting all his preferred positions.
<CAi> denotes his CA at <posi>.
<PAi> denotes his PA at <posi>.
(0<=|P Ai|,|C Ai|<=1000,note P A and CA can be negative here.)
After the description of the player list, the following line will give an integer M (0<=M<=N (N - 1)), which indicates the number of relationships between the teammates. Then each of the following M lines is shown in the following format:
<SquadNumA> <SquadNumB > Like/Dislike <value>
Here:
<SquadNumA> denotes Player A’s Squad Number.
<SquadNumB> denotes Player B’s Squad Number.
Like/Dislike denotes the property of the relationship.
<value> denotes that when both of them appear in your starting line-up, the CA of line-up will be increased/decreased by value(0<=value<=100).
No two relationships of the same pair of teammates will occur.
The last line of each test case shows the formation that you have determined. We guarantee that the formation is legal.
You may take the sample for more details.
For each test case, the first line contains an integer N (1<=N<=20), the total number of players in your team.
Each of the following N lines describe a player in the following format:
<SquadNum> <PositionNum> <pos1> <CA1> <PA1> <pos2> <CA2> <PA2> . . . <posnum><CAnum><PAnum>
Here:
<SquadNum> denotes the player’s unique squad number (between 1 and 99, inclusive).
<PositionNum> denotes the number of positions he preferred.
<pos1> <pos2> . . . <posnum> are strings chosen in {GK, DF, MF, ST},denoting all his preferred positions.
<CAi> denotes his CA at <posi>.
<PAi> denotes his PA at <posi>.
(0<=|P Ai|,|C Ai|<=1000,note P A and CA can be negative here.)
After the description of the player list, the following line will give an integer M (0<=M<=N (N - 1)), which indicates the number of relationships between the teammates. Then each of the following M lines is shown in the following format:
<SquadNumA> <SquadNumB > Like/Dislike <value>
Here:
<SquadNumA> denotes Player A’s Squad Number.
<SquadNumB> denotes Player B’s Squad Number.
Like/Dislike denotes the property of the relationship.
<value> denotes that when both of them appear in your starting line-up, the CA of line-up will be increased/decreased by value(0<=value<=100).
No two relationships of the same pair of teammates will occur.
The last line of each test case shows the formation that you have determined. We guarantee that the formation is legal.
You may take the sample for more details.
Output
For each test case, you should output two integers in a line, the best CA and PA of your line-up. If you can even not round up your line-up, please output “Poor Manager!” (without quotes)
Sample Input
2 15 1 1 GK 150 160 2 1 DF 150 160 3 1 DF 150 160 4 1 DF 150 160 5 1 DF 150 160 6 1 MF 150 160 7 1 MF 150 160 8 1 MF 150 160 9 1 ST 150 160 10 1 MF 150 160 11 1 ST 150 160 12 1 GK 130 150 13 1 DF 130 150 14 1 MF 130 150 15 1 ST 130 150 2 15 9 Like 10 2 13 Dislike 20 4-4-2 11 1 1 GK 150 160 2 1 DF 150 160 3 1 DF 150 160 4 1 DF 150 160 5 1 DF 150 160 6 1 MF 150 160 7 1 MF 150 160 8 1 MF 150 160 9 1 ST 150 160 10 1 MF 150 160 11 1 ST 150 160 0 4-3-3
Sample Output
1650 1760 Poor Manager!
Author
BUPT
Source
2014 Multi-University Training Contest 6
思路：先dfs枚举出所有选11个人作为队员的情况，枚举出来之后如果最大的可能都不够ansc大或者不能构成足球队的话就直接返回，之后再用DP求出最大值。
#include <stdio.h>
#define INF 99999999
#define max(A,B)(A>B?A:B)
struct S{
int c[4],p[4],mx;
bool flag[4];
}node[20];
int n,hash[100],add[20][20],a,b,c,ansc,ansp,df,mf,st,gk,attach,dpc[13][3][13][13],dpp[13][3][13][13],sel[13];
void dfs(int now,int cnt)
{
if(cnt==11)
{
int i,j,k,l,mx;
attach=0;
for(i=0;i<11;i++) for(j=0;j<11;j++) attach+=add[sel[i]][sel[j]];
mx=0;
for(i=0;i<11;i++) mx+=node[sel[i]].mx;
if(mx+attach<ansc) return;//最优化剪枝
gk=df=mf=st=0;
for(i=0;i<11;i++)
{
if(node[sel[i]].flag[0]) gk++;
if(node[sel[i]].flag[1]) df++;
if(node[sel[i]].flag[2]) mf++;
if(node[sel[i]].flag[3]) st++;
}
if(gk<1 || df<a || mf<b || st<c) return;//不能构成足球队
for(i=0;i<=11;i++) for(j=0;j<=1;j++) for(k=0;k<=a;k++) for(l=0;l<=b;l++) dpc[i][j][k][l]=-INF;
dpc[0][0][0][0]=dpp[0][0][0][0]=0;
for(i=0;i<11;i++)
{
for(j=0;j<=1;j++)
{
for(k=0;k<=a;k++)
{
for(l=0;l<=b;l++)
{
if(dpc[i][j][k][l]!=-INF)
{
if(node[sel[i]].flag[0])
{
if(dpc[i+1][j+1][k][l]<dpc[i][j][k][l]+node[sel[i]].c[0])
{
dpc[i+1][j+1][k][l]=dpc[i][j][k][l]+node[sel[i]].c[0];
dpp[i+1][j+1][k][l]=dpp[i][j][k][l]+node[sel[i]].p[0];
}
else if(dpc[i+1][j+1][k][l]==dpc[i][j][k][l]+node[sel[i]].c[0])
{
dpp[i+1][j+1][k][l]=max(dpp[i][j][k][l]+node[sel[i]].p[0],dpp[i+1][j+1][k][l]);
}
}
if(node[sel[i]].flag[1])
{
if(dpc[i+1][j][k+1][l]<dpc[i][j][k][l]+node[sel[i]].c[1])
{
dpc[i+1][j][k+1][l]=dpc[i][j][k][l]+node[sel[i]].c[1];
dpp[i+1][j][k+1][l]=dpp[i][j][k][l]+node[sel[i]].p[1];
}
else if(dpc[i+1][j][k+1][l]==dpc[i][j][k][l]+node[sel[i]].c[1])
{
dpp[i+1][j][k+1][l]=max(dpp[i][j][k][l]+node[sel[i]].p[1],dpp[i+1][j][k+1][l]);
}
}
if(node[sel[i]].flag[2])
{
if(dpc[i+1][j][k][l+1]<dpc[i][j][k][l]+node[sel[i]].c[2])
{
dpc[i+1][j][k][l+1]=dpc[i][j][k][l]+node[sel[i]].c[2];
dpp[i+1][j][k][l+1]=dpp[i][j][k][l]+node[sel[i]].p[2];
}
else if(dpc[i+1][j][k][l+1]==dpc[i][j][k][l]+node[sel[i]].c[2])
{
dpp[i+1][j][k][l+1]=max(dpp[i][j][k][l]+node[sel[i]].p[2],dpp[i+1][j][k][l+1]);
}
}
if(node[sel[i]].flag[3])
{
if(dpc[i+1][j][k][l]<dpc[i][j][k][l]+node[sel[i]].c[3])
{
dpc[i+1][j][k][l]=dpc[i][j][k][l]+node[sel[i]].c[3];
dpp[i+1][j][k][l]=dpp[i][j][k][l]+node[sel[i]].p[3];
}
else if(dpc[i+1][j][k][l]==dpc[i][j][k][l]+node[sel[i]].c[3])
{
dpp[i+1][j][k][l]=max(dpp[i][j][k][l]+node[sel[i]].p[3],dpp[i+1][j][k][l]);
}
}
}
}
}
}
}
dpc[11][1][a][b]+=attach;
if(ansc<dpc[11][1][a][b]) ansc=dpc[11][1][a][b],ansp=dpp[11][1][a][b];
else if(ansc==dpc[11][1][a][b]) ansp=max(dpp[11][1][a][b],ansp);
return;
}
if(now>=n || cnt+n-now<11) return;
sel[cnt]=now;
dfs(now+1,cnt+1);//选
dfs(now+1,cnt);//不选
}
int main()
{
int T,i,j,t,id,val;
char s[5];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&t);
hash[t]=i;
for(j=0;j<4;j++) node[i].flag[j]=0;
node[i].mx=-INF;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
if(s[0]=='G') id=0;
else if(s[0]=='D') id=1;
else if(s[0]=='M') id=2;
else id=3;
scanf("%d%d",&node[i].c[id],&node[i].p[id]);
node[i].mx=max(node[i].mx,node[i].c[id]);
node[i].flag[id]=1;
}
}
scanf("%d",&t);
for(i=0;i<n;i++) for(j=0;j<n;j++) add[i][j]=0;
while(t--)
{
scanf("%d%d%s%d",&a,&b,s,&val);
if(s[0]=='D') add[hash[a]][hash[b]]=-val;
else add[hash[a]][hash[b]]=val;
}
scanf("%d-%d-%d",&a,&b,&c);
ansc=ansp=-INF;
dfs(0,0);
if(ansc>-INF) printf("%d %d\n",ansc,ansp);
else printf("Poor Manager!\n");
}
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。