求大佬帮我查查错!!

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

dinghongyu @ 2019-01-29 12:21:08

3一直过不了,也看不出哪里错了,求大佬帮忙调试

#include <bits/stdc++.h>
using namespace std;
int n,m,f[32001];
int v1,p1,q1;
struct _
{
    int v,w,q;               //v,价值;w,乘积 
    int num,fj[3][3];      //num,附件数;fj,附件信息:fj[i][1],价值;fj[i][2],乘积 
}a[61];
bool b[61];
int main()
{
    cin >> n >> m;
    for (int i = 1;i <= m;i++)
    {
        cin >> v1 >> p1 >> q1;
        if (!q1)              //主件
            a[i].v = v1,a[i].w = v1 * p1;
        else                  //附件
            a[q1].num++,a[q1].fj[a[q1].num][1] = v1,a[q1].fj[a[q1].num][2] = v1 * p1,b[i] = 1;
    }
    for (int i = 1;i <= m;i++)
    {
        for (int j = n;j >= a[i].v;j--)
        {
            if (b[i])
                continue;                           //是附件 
            f[j] = max(f[j],f[j - a[i].v] + a[i].w);//仅购主件 
            if (a[i].num)
            {
                if (j >= a[i].v + a[i].fj[1][1] + a[i].fj[2][1])
                    f[j] = max(f[j],f[j - a[i].v - a[i].fj[1][1] - a[i].fj[2][1]] + a[i].w + a[i].fj[1][2] + a[i].fj[2][2]);//购买主件,附件1和附件2 
                if (j >= a[i].v + a[i].fj[1][1])
                    f[j] = max(f[j],f[j - a[i].v - a[i].fj[1][1]] + a[i].v + a[i].fj[1][2]);//购买主件+附件1 
                if (j >= a[i].v + a[i].fj[2][1])
                    f[j] = max(f[j],f[j - a[i].v - a[i].fj[2][1]] + a[i].v + a[i].fj[2][2]);//购买主件+附件2 
            }
        }
    }
    cout << f[n];
    return 0;
}

by dinghongyu @ 2019-01-29 12:24:57

第三个点A不了。。。


by chenyanming @ 2019-01-29 12:30:27

如果不买呢


by dinghongyu @ 2019-01-29 12:43:49

不买就是等于f_j啊,因为j > a_i.v,所以不会买不了主件


by dinghongyu @ 2019-01-29 12:43:55

@chenyanming


|