P1064帮忙看一下谢谢大佬,大佬大气!!!

P1064 [NOIP2006 提高组] 金明的预算方案

xuzhenghao @ 2019-03-03 19:31:00

哪位大佬帮忙看一下哪儿错了谢谢(P1064金明的预算方案) 祝他(她)天天大吉

include <bits/stdc++.h>

using namespace std;

struct Point

{

int v, p;//分别表示价格和重要度 
int attv[3], attp[3];
//attv表示第k个附件的价格,attp表示第k个附件的重要度 
int k;//当前有k个附件 

};

Point a[70];

int n, m, f[40000];

int cnt;//主件的个数

//分五种情况

//1.不选,然后去考虑下一个

//2.选且只选这个主件

//3.选这个主件,并且选附件1

//4.选这个主件,并且选附件2

//5.选这个主件,并且选附件1和附件2.

int max_five(int i, int j)

{

int maxn = 0;

maxn = max (maxn, f[j]);//不选 

if (j - a[i].v >= 0) maxn = max (maxn, f[j - a[i].v] + a[i].v * a[i].p);//如果放得下只选主件 

if (j - a[i].v - a[i].attv[1] >= 0) maxn = max (maxn, f[j - a[i].v - a[i].attv[1]] + a[i].v * a[i].p + a[i].attv[1] * a[i].attp[1]);

//如果放得下只选主件和附件1 

if (j - a[i].v - a[i].attv[2] >= 0 )maxn = max (maxn, f[j - a[i].v - a[i].attv[2]] + a[i].v * a[i].p + a[i].attv[2] * a[i].attp[2]);

//如果放得下只选主件和附件2 

if (j - a[i].v - a[i].attv[1] - a[i].attv[2] >= 0)

    maxn = max (maxn, f[j - a[i].v - a[i].attv[1] - a[i].attv[2]] + a[i].v * a[i].p + a[i].attv[1] * a[i].attp[1] + a[i].attv[2] * a[i].attp[2]);

    //如果放得下选主件、附件1和附件2 

return maxn;

}

int main ()

{

cin >> n >> m;//输入 

for (int i = 1; i <= m; i++)

{

    int x, y, z;

    cin >> x >> y >> z;

    if (z == 0)

    {

        cnt++;

        a[cnt].v = x;

        a[cnt].p = y;

    }

    //如果是主件,就放入第cnt个主件中 

    else

    {

        a[z].k++;

        a[z].attv[a[z].k] = x;

        a[z].attp[a[z].k] = y;

    }

    //如果是附件,就放入第cnt个主件中的附件中 

}

for (int i = 1; i <= m; i++)

{

    for (int j = 0; j <= cnt; j++)

    {

        f[j] = max_five (i, j);

    }

}

for (int i = 1; i <= cnt; i++) cout << f[i] 
<< " "; 

cout << f[cnt] << endl;

return 0;

}


by xuzhenghao @ 2019-11-08 11:07:36

@小Fun·Foxy 谢谢大佬,大佬大气


上一页 |