noip模拟赛 党

分析：一道非常恶心的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<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

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
", ans0, ans1, ans2);

    return 0;
}