分析：一道非常恶心的dp题.每个人要么选或不选，很像是0-1背包,可以套用背包问题的状态，但是因为题目要求3个值，所以可以再加一维表示3个答案.
f[i][j][k][l][p][0/1/2]表示i个守门员，j个后卫，k个中锋,l个前锋，花费是p,最后一维是0则表示不考虑队长的价值，1是方案数，2是队长价值.在这个状态表示里省去了一维表示前多少个人，其实就是一个滚动数组，递推的时候要倒序枚举.因为队长的价值会被算两边，所以队长肯定是价值最大的，先对所有人排个序，枚举到第i个人的时候，就让第i个人当队长就行了，不需要再去枚举.然后根据题目说的那样更新0/1/2就可以了.
#include#include #include #include using namespace std;const int mod = 1000000000, inf = 0x7fffffff;int n, up[10], down[10], f[2][6][6][4][1010][3], ans0, ans1 = inf, ans2;int maxn;struct node{ int id, v, c;}e[510];bool cmp(node a, node b){ return a.v < b.v;}void init(){ up[1] = 1; down[1] = 1; up[2] = 5; down[2] = 3; up[3] = 5; down[3] = 2; up[4] = 3; down[4] = 1;}void update(int i, int j, int k, int l,int p,int fangan, int jiazhi, int duizhang){ if (f[i][j][k][l][p][0] < jiazhi) { f[i][j][k][l][p][0] = jiazhi; f[i][j][k][l][p][1] = 0; f[i][j][k][l][p][2] = duizhang; } if (f[i][j][k][l][p][0] == jiazhi && f[i][j][k][l][p][2] < duizhang) { f[i][j][k][l][p][1] = 0; f[i][j][k][l][p][2] = duizhang; } if (f[i][j][k][l][p][0] == jiazhi && f[i][j][k][l][p][2] == duizhang) { f[i][j][k][l][p][1] += fangan; if (f[i][j][k][l][p][1] >= mod) f[i][j][k][l][p][1] = mod; }}void gengxin(int x){ for (int i = up[1] - (e[x].id == 1); i >= 0; i--) for (int j = up[2] - (e[x].id == 2); j >= 0; j--) for (int k = up[3] - (e[x].id == 3); k >= 0; k--) for (int l = up[4] - (e[x].id == 4); l >= 0; l--) if (i + j + k + l < 11) { for (int p = maxn - e[x].c; p >= 0; p--) if (f[i][j][k][l][p][1]) update(i + (e[x].id == 1), j + (e[x].id == 2), k + (e[x].id == 3), l + (e[x].id == 4), p + e[x].c,f[i][j][k][l][p][1], f[i][j][k][l][p][0] + e[x].v, e[x].v); }}int main(){ init(); f[0][0][0][0][0][2] = -1; f[0][0][0][0][0][1] = 1; scanf("%d", &n); for (int i = 1; i <= n; i++) { char s[20]; scanf("%s", s + 1); scanf("%d%d", &e[i].v, &e[i].c); if (s[1] == 'G') e[i].id = 1; if (s[1] == 'D') e[i].id = 2; if (s[1] == 'M') e[i].id = 3; if (s[1] == 'F') e[i].id = 4; } scanf("%d", &maxn); sort(e + 1, e + 1 + n,cmp); for (int i = 1; i <= n; i++) gengxin(i); for (int i = down[1]; i <= up[1]; i++) for (int j = down[2]; j <= up[2]; j++) for (int k = down[3]; k <= up[3]; k++) for (int l = down[4]; l <= up[4]; l++) if (i + j + k + l == 11) for (int p = 0; p <= maxn; p++) if (f[i][j][k][l][p][1]) { int temp0 = f[i][j][k][l][p][0] + f[i][j][k][l][p][2]; int temp1 = p; int temp2 = f[i][j][k][l][p][1]; if (temp0 > ans0) { ans2 = 0; ans0 = temp0; ans1 = temp1; } if (temp0 == ans0 && temp1 < ans1) { ans1 = temp1; ans2 = 0; } if (temp0 == ans0 && temp1 == ans1) { ans2 += temp2; if (ans2 >= mod) ans2 = mod; } } printf("%d %d %d\n", ans0, ans1, ans2); return 0;}