C++与Pascal的题解在下方

【问题描述】 你现在希望组建一支足球队，一支足球队一般来说由11人组成。这11人有四 种不同的职业：守门员、后卫、中锋、前锋组成。你在组队的时候必须满足以下规则：

1、 足球队恰好由11人组成。

2、 11人中恰好有一名守门员，3-5 名后卫，2-5 名中锋，1-3 名前锋。

3、 你需要从这11人中选出一名队长。

4、 你这个足球队的价值是11人的价值之和再加上队长的价值，也就是说 队长的价值会被计算两次。

5、 你这个足球队的花费是11人的花费之和，你的花费之和不能超过给定的上限。

现在告诉你球员的总数，每个球员的职业、价值、花费，以及花费的上限， 你希望在满足要求的情况下，达到以下目标：

1、 最大化队伍的价值。

2、 在最大化队伍的价值的情况下，最小化队伍的花费。

3、 在满足以上两个要求的情况下，有多少种选择球员的方案。

如果有两种方案它们的区别仅仅是队长不一样，那么这两种方案应该被认为是一种方案。 你的任务是输出这三个值：价值、花费、方案数。

【输入格式】 第一行一个正整数?，代表可选的球员个数。 接下来?行，每行描述一个球员的信息。每行开始是一个字符串，可能的字 符串有 Goalkeeper、Defender、Midfielder、Forward，分别代表该球员的职业是守 门员、后卫、中锋、前锋。接下来两个数?,?，分别代表该球员的价值和花费。 最后一行一个整数，代表花费的上限。 数据保证一定存在一种解。

【输出格式】 一行三个整数，分表代表最大价值、最小花费和方案数。如果方案数超过了 109，则直接输出109。

【样例输入】

15

Defender 23 45

Midfielder 178 85

Goalkeeper 57 50

Goalkeeper 57 50

Defender 0 45

Forward 6 60

Midfielder 20 50

Goalkeeper 0 50

Midfielder 64 65

Midfielder 109 70

Forward 211 100

Defender 0 40

Defender 29 45

Midfielder 57 60

Defender 52 45 600

【样例输出】 716 600 2

【样例解释】 选择所有的五名后卫，选择价值为178,20,64,109的中锋和价值为6的前锋， 两名守门员任意选择。选择价值为178的中锋作为队长。

【数据规模与约定】 对于30%的数据，? ≤ 20。 对于60%的数据，费用上限足够大。 对于100%的数据，1 ≤ ? ≤ 500，所有球员的价值和花费以及花费上限均在 [0,1000]。

 

题解1(C++)

f[i1][i2][i3][i4][i5][i6]

i1:门将

i2:后卫

i3:中场

i4:前锋

i5:当前花费

i6:[0]:球员价值和;[1]:取最大值时情况个数[2]:队长价值

dp即可

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5   6 using namespace std;  7   8 const int mo=1000000000;  9  10 int n,limit[10],up,down[10]; 11  12 char s[100]; 13  14 int f[2][6][6][4][1010][3]; 15  16 struct rec 17 { 18     int opt,v,c; 19     bool operator<(const rec &a)const 20     { 21         return v
          
           mo) f[a][b][c][d][e][1]=mo; 43     } 44 } 45  46 void update(int p) 47 { 48     for (int a=limit[0]-(z[p].opt==0);a>=0;a--) 49         for (int b=limit[1]-(z[p].opt==1);b>=0;b--) 50             for (int c=limit[2]-(z[p].opt==2);c>=0;c--) 51                 for (int d=limit[3]-(z[p].opt==3);d>=0;d--) 52                     if (a+b+c+d<11) 53                     { 54                         for (int e=up-z[p].c;e>=0;e--) 55                             if (f[a][b][c][d][e][1]) 56                             { 57                                 int newv=f[a][b][c][d][e][0]+z[p].v; 58                                 update(a+(z[p].opt==0),b+(z[p].opt==1),c+(z[p].opt==2),d+(z[p].opt==3),e+z[p].c,newv,f[a][b][c][d][e][1],z[p].v); 59                             } 60                     } 61 } 62  63 int main() 64 { 65     freopen("wosa.in","r",stdin); 66     freopen("wosa.out","w",stdout); 67  68     int test; 69     test=1; 70     for (;test--;) 71     { 72         scanf("%d",&n); 73         down[0]=1;down[1]=3;down[2]=2;down[3]=1; 74         limit[0]=1;limit[1]=5;limit[2]=5;limit[3]=3; 75         memset(f,0,sizeof(f)); 76         f[0][0][0][0][0][1]=1; 77         f[0][0][0][0][0][2]=-1; 78         for (int a=1;a<=n;a++) 79         { 80             scanf("%s",s); 81             int v,c; 82             scanf("%d%d",&v,&c); 83             if (s[0]=='G') z[a].opt=0; 84             if (s[0]=='D') z[a].opt=1; 85             if (s[0]=='M') z[a].opt=2; 86             if (s[0]=='F') z[a].opt=3; 87             z[a].v=v;z[a].c=c; 88         } 89         scanf("%d",&up); 90         sort(z+1,z+n+1); 91         for (int a=1;a<=n;a++) 92             update(a); 93         int resv=0,resc=0x3f3f3f3f,resn=0; 94         for (int a=down[0];a<=limit[0];a++) 95             for (int b=down[1];b<=limit[1];b++) 96                 for (int c=down[2];c<=limit[2];c++) 97                     for (int d=down[3];d<=limit[3];d++) 98                         if (a+b+c+d==11) 99                             for (int e=0;e<=up;e++)100                                 if (f[a][b][c][d][e][1])101                                 {102                                     int nowv=f[a][b][c][d][e][0]+f[a][b][c][d][e][2];103                                     int nowc=e;104                                     int nown=f[a][b][c][d][e][1];105                                     if (nowv>resv)106                                     {107                                         resv=nowv;108                                         resc=nowc;109                                         resn=0;110                                     }111                                     if (nowv==resv && nowc
           
            mo) resn=mo;120 }121 }122 printf("%d %d %d\n",resv,resc,resn);123 }124 125 return 0;126 }
           
          
         
        
       
      

 

题解2(Pascal)

1 1.枚举所有可能的forward,midfielder,denfender组合情况  2 2.对每种球员按优先度排序  3 3.对每一种组合情况枚举然后比较即可  4   5 TYPE    rec=record V,D,N:int64;end;  6 CONST   TEAM:array[1..8,1..3] of int64=((3,4,3),(3,5,2),(4,3,3),(4,4,2),(4,5,1),(5,2,3),(5,3,2),(5,4,1));  7         INFINITE=1000000000;  8 VAR     V,D:array[1..3,1..500] of int64;  9         C:array[1..500,0..500] of int64; 10         ANS:array[1..8] of rec; 11         t:array[1..3] of int64; 12         flag:array[1..8] of boolean; 13         i,j,k:longint; 14         y,N,p,t1,t2,t3,v0,d0,p0,maxv,mind,max1,min1,captain:int64; 15         s,s0:string; 16  17 FUNCTION        min(x,y:int64):int64;BEGIN if x
      
       A1) or ((V[x][j]=A1) and (D[x][j]>A2)) then begin R:=j;break;end; 24         if R
       
        INFINITE then ANS[i].N:=INFINITE; 27 END; 28 BEGIN 29         readln(N);mind:=INFINITE; 30         for i:=1 to 500 do C[i][i]:=1; 31         for i:=1 to 500 do C[i][0]:=1; 32         for i:=2 to 500 do for j:=1 to i-1 do C[i][j]:=min(INFINITE,C[i-1][j-1]+C[i-1][j]); 33         for i:=1 to N do begin 34                 readln(s); 35                 if s[1]='D' then begin 36                         inc(t[1]); 37                         s0:=copy(s,10,length(s)-9); 38                         p:=pos(' ',s0); 39                         val(copy(s0,1,p-1),V[1][t[1]]); 40                         val(copy(s0,p+1,length(s0)-p),D[1][t[1]]); 41                 end; 42                 if s[1]='M' then begin 43                         inc(t[2]); 44                         s0:=copy(s,12,length(s)-11); 45                         p:=pos(' ',s0); 46                         val(copy(s0,1,p-1),V[2][t[2]]); 47                         val(copy(s0,p+1,length(s0)-p),D[2][t[2]]); 48                 end; 49                 if s[1]='F' then begin 50                         inc(t[3]); 51                         s0:=copy(s,9,length(s)-8); 52                         p:=pos(' ',s0); 53                         val(copy(s0,1,p-1),V[3][t[3]]); 54                         val(copy(s0,p+1,length(s0)-p),D[3][t[3]]); 55                 end; 56                 if s[1]='G' then begin 57                         s0:=copy(s,12,length(s)-11); 58                         p:=pos(' ',s0); 59                         val(copy(s0,1,p-1),v0); 60                         val(copy(s0,p+1,length(s0)-p),d0); 61                         if (maxv=v0) and (mind=d0) then inc(p0) else begin 62                                 if maxv=v0 then begin 63                                         if mind>d0 then begin 64                                                 mind:=d0; 65                                                 p0:=1; 66                                         end; 67                                 end; 68                                 if maxv
        
         D[i][k])) then begin 77                 y:=V[i][j];V[i][j]:=V[i][k];V[i][k]:=y; 78                 y:=D[i][j];D[i][j]:=D[i][k];D[i][k]:=y; 79         end; 80         for i:=1 to 8 do ANS[i].N:=1; 81         for i:=1 to 8 do if (TEAM[i][1]<=t[1]) and (TEAM[i][2]<=t[2]) and (TEAM[i][3]<=t[3]) then flag[i]:=true; 82         for i:=1 to 8 do if flag[i] then begin 83                 t1:=TEAM[i][1]; 84                 t2:=TEAM[i][2]; 85                 t3:=TEAM[i][3]; 86                 if (t1<=t[1]) and (t2<=t[2]) and (t3<=t[3]) then begin 87                         for k:=1 to t1 do inc(ANS[i].V,V[1][k]); 88                         for k:=1 to t1 do inc(ANS[i].D,D[1][k]); 89                         for k:=1 to t2 do inc(ANS[i].V,V[2][k]); 90                         for k:=1 to t2 do inc(ANS[i].D,D[2][k]); 91                         for k:=1 to t3 do inc(ANS[i].V,V[3][k]); 92                         for k:=1 to t3 do inc(ANS[i].D,D[3][k]); 93                         cal(1,t1,V[1][t1],D[1][t1]); 94                         cal(2,t2,V[2][t2],D[2][t2]); 95                         cal(3,t3,V[3][t3],D[3][t3]); 96                 end; 97         end;p:=0; 98         for i:=1 to 8 do if flag[i] then if max1
         
          ANS[i].D then min1:=ANS[i].D;100         for i:=1 to 8 do if flag[i] then if (max1=ANS[i].V) and (min1=ANS[i].D) then inc(p,ANS[i].N);101         p:=p*p0;102         captain:=maxv;103         for i:=1 to 3 do if captain
          
           INFINITE then p:=INFINITE;105         writeln(max1+maxv+captain,' ',min1+mind,' ',p);106 END.
          
         
        
       
      

 

附上两篇 神犇AC 的博客