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 = , inf = 0x7fffffff;

int n, up[], down[], f[][][][][][], ans0, ans1 = inf, ans2;

int maxn;

struct node

{

    int id, v, c;

}e[];

bool cmp(node a, node b)

{

    return a.v < b.v;

}

void init()

{

    up[] = ;

    down[] = ;

    up[] = ;

    down[] = ;

    up[] = ;

    down[] = ;

    up[] = ;

    down[] = ;

}

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][] < jiazhi)

    {

        f[i][j][k][l][p][] = jiazhi;

        f[i][j][k][l][p][] = ;

        f[i][j][k][l][p][] = duizhang;

    }

    if (f[i][j][k][l][p][] == jiazhi && f[i][j][k][l][p][] < duizhang)

    {

        f[i][j][k][l][p][] = ;

        f[i][j][k][l][p][] = duizhang;

    }

    if (f[i][j][k][l][p][] == jiazhi && f[i][j][k][l][p][] == duizhang)

    {

        f[i][j][k][l][p][] += fangan;

        if (f[i][j][k][l][p][] >= mod)

            f[i][j][k][l][p][] = mod;

    }

}

void gengxin(int x)

{

    for (int i = up[] - (e[x].id == ); i >= ; i--)

        for (int j = up[] - (e[x].id == ); j >= ; j--)

            for (int k = up[] - (e[x].id == ); k >= ; k--)

                for (int l = up[] - (e[x].id == ); l >= ; l--)

                    if (i + j + k + l < )

                    {

                        for (int p = maxn - e[x].c; p >= ; p--)

                            if (f[i][j][k][l][p][])

                            update(i + (e[x].id == ), j + (e[x].id == ), k + (e[x].id == ), l + (e[x].id == ), p + e[x].c,f[i][j][k][l][p][], f[i][j][k][l][p][] + e[x].v, e[x].v);

                    }

}

int main()

{

    init();

    f[][][][][][] = -;

    f[][][][][][] = ;

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

    {

        char s[];

        scanf("%s", s + );

        scanf("%d%d", &e[i].v, &e[i].c);

        if (s[] == 'G')

            e[i].id = ;

        if (s[] == 'D')

            e[i].id = ;

        if (s[] == 'M')

            e[i].id = ;

        if (s[] == 'F')

            e[i].id = ;

    }

    scanf("%d", &maxn);

    sort(e + , e +  + n,cmp);

    for (int i = ; i <= n; i++)

        gengxin(i);

    for (int i = down[]; i <= up[]; i++)

        for (int j = down[]; j <= up[]; j++)

            for (int k = down[]; k <= up[]; k++)

                for (int l = down[]; l <= up[]; l++)

                        if (i + j + k + l == )

                            for (int p = ; p <= maxn; p++)

                                if (f[i][j][k][l][p][])

                            {

                        int temp0 = f[i][j][k][l][p][] + f[i][j][k][l][p][];

                        int temp1 = p;

                        int temp2 = f[i][j][k][l][p][];

                        if (temp0 > ans0)

                        {

                            ans2 = ;

                            ans0 = temp0;

                            ans1 = temp1;

                        }

                        if (temp0 == ans0 && temp1 < ans1)

                        {

                            ans1 = temp1;

                            ans2 = ;

                        }

                        if (temp0 == ans0 && temp1 == ans1)

                        {

                            ans2 += temp2;

                            if (ans2 >= mod)

                                ans2 = mod;

                        }

                    }

    printf("%d %d %d\n", ans0, ans1, ans2);

    return ;

}

巴特西

noip模拟赛党

最新文章

热门文章

巴特西

noip模拟赛 党

最新文章

热门文章

noip模拟赛党