60分代码求助

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

echo2001 @ 2019-11-20 13:10:57

//有依赖的背包问题
//金明的预算方案 NOIP 2006 提高组 第二题

//思路:转化为01背包问题.不过决策变为了1、不买这个主件;2、买这个主件,同时附件的购买还有四种情况
#include <iostream>
using namespace std;

int best[32000][240] = {0};

struct item_group
{
    int main_v = 0;
    int main_p = 0;
    int main_vp = 0;
    int surbordinate[3][3] = {0};
};

item_group group[61];
int maximum(int x, int y)
{
    if (x > y)
        return x;
    return y;
}

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    int v = 0, p = 0, q = 0;
    //input;
    int num = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> v >> p >> q;
        if (q == 0)
        {
            num++;
            group[num].main_p = p;
            group[num].main_v = v;
            group[num].main_vp = v * p;
        }
        else
        {
            if (group[q].surbordinate[1][0] == 0) //这是第一个附件
            {
                group[q].surbordinate[1][0] = v;
                group[q].surbordinate[1][1] = p;
                group[q].surbordinate[1][2] = v * p;
            }
            else //这是第二个附件
            {
                group[q].surbordinate[2][0] = v;
                group[q].surbordinate[2][1] = p;
                group[q].surbordinate[2][2] = v * p;
            }
        }
    }
    //开始dp
    int temp = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= num; j++)
        {
            //决策有五种可能
            best[i][j] = best[i][j - 1];
            if (i - group[j].main_v >= 0)
            {
                temp = best[i - group[j].main_v][j - 1] + group[j].main_vp;
                best[i][j] = maximum(best[i][j], temp);
            }
            if (i - group[j].main_v - group[j].surbordinate[1][0] >= 0)
            {
                temp = best[i - group[j].main_v - group[j].surbordinate[1][0]][j - 1] + group[j].main_vp + group[j].surbordinate[1][2];
                best[i][j] = maximum(best[i][j], temp);
            }
            if (i - group[j].main_v - group[j].surbordinate[2][0] >= 0)
            {
                temp = best[i - group[j].main_v - group[j].surbordinate[2][0]][j - 1] + group[j].main_vp + group[j].surbordinate[2][2];
                best[i][j] = maximum(best[i][j], temp);
            }
            if (i - group[j].main_v - group[j].surbordinate[1][0] - group[j].surbordinate[2][0] >= 0)
            {
                temp = best[i - group[j].main_v - group[j].surbordinate[1][0] - group[j].surbordinate[2][0]][j - 1] + group[j].main_vp + group[j].surbordinate[1][2] + group[j].surbordinate[2][2];
                best[i][j] = maximum(best[i][j], temp);
            }
        }

    }
    cout << best[n][num] << endl;
    return 0;
}

|