xuzhenghao @ 2019-03-03 19:31:00
哪位大佬帮忙看一下哪儿错了谢谢(P1064金明的预算方案) 祝他(她)天天大吉
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 谢谢大佬,大佬大气