题解 | #购物单#

考虑三种情况，取三种情况的最大解。

1. 不买配件
2. 买A或B一个配件
3. 买A和B两个配件

   // https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37
   // 购物单
   #include <math.h>
   #include <stdio.h>
   #include <string.h>
   #include <stdbool.h>
   #include <stdlib.h>
   

int main()
{
int MY_INT_MAX = -1;
int money, num;
scanf("%d %d", &money, &num);
int food[num][3];
memset(food, 0, sizeof(food));
for (int i = 0; i < num; i++)
{
scanf("%d %d %d", &food[i][0], &food[i][1], &food[i][2]);
}

int hash[num][3];
memset(hash, 0, sizeof(hash));
for (int i = 0; i < num; i++)
{
    for (int j = 0; j < 3; j++)
    {
        hash[i][j] = MY_INT_MAX;
    }
}
for (int i = 0; i < num; i++)
{
    if (food[i][2] == 0) // it is main object
    {
        hash[i][0] = 1;
    }
    else
    {
        int id = food[i][2] - 1;
        if (hash[id][1] == MY_INT_MAX)
        {
            hash[id][1] = i;
        }
        else
        {
            hash[id][2] = i;
        }
    }
}

int dp[money + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < num; i++)
{
    for (int j = money; j >= food[i][0]; j--)
    {
        if (hash[i][0] == 1) // it is main object
        {
            int subId1 = hash[i][1];
            int subId2 = hash[i][2];
            int subVal1 = 0;
            int subImp1 = 0;
            int subVal2 = 0;
            int subImp2 = 0;
            if (subId1 != MY_INT_MAX)
            {
                subVal1 = food[subId1][0];
                subImp1 = food[subId1][1];
            }
            if (subId2 != MY_INT_MAX)
            {
                subVal2 = food[subId2][0];
                subImp2 = food[subId2][1];
            }
            int dp0 = 0;
            int dp1 = 0;
            int dp2 = 0;
            int dp3 = 0;
            // case 1: donot buy attachment
            dp0 = fmax(dp[j], dp[j - food[i][0]] + food[i][0] * food[i][1]);
            // case 2: buy one attachment
            if (j - food[i][0] - subVal1 >= 0)
            {
                dp1 = fmax(dp[j], dp[j - food[i][0] - subVal1] + food[i][0] * food[i][1] + subVal1 * subImp1);
            }
            // case 2: buy another one attachment
            if (j - food[i][0] - subVal2 >= 0)
            {
                dp2 = fmax(dp[j], dp[j - food[i][0] - subVal2] + food[i][0] * food[i][1] + subVal2 * subImp2);
            }
            // case 3" buy both two attachment
            if (j - food[i][0] - subVal1 - subVal2 >= 0)
            {
                dp3 = fmax(dp[j], dp[j - food[i][0] - subVal1 - subVal2] + food[i][0] * food[i][1] + subVal1 * subImp1 + subVal2 * subImp2);
            }
            dp[j] = fmax(fmax(dp0, dp1), fmax(dp2, dp3));
        }
    }
}

printf("%d\n", dp[money]);
return 0;

}
```