题解 | 购物单 - 26年-有注释帮助理解

using System;
using System.Collections.Generic;
using System.Linq;

public class Program {
    public static void Main() {
        var money_number = Console.ReadLine().Split(" ");
        int money = Convert.ToInt32(money_number[0]);
        int number = Convert.ToInt32(money_number[1]);
        Good[] allGoods = new Good[number];
        for (int i = 0; i < number; i++) {
            var input = Console.ReadLine().Split(" ");
            int price = Convert.ToInt32(input[0]);
            int value = Convert.ToInt32(input[1]) * price;
            int index = Convert.ToInt32(input[2]);
            Good good = new Good(price, value, index);
            allGoods[i] = good;
        }

        for (int i = 0; i < allGoods.Length; i++) {
            Good currentGood = allGoods[i];
            if (currentGood.MainIndex == 0) {
                continue;
            } else {
                //Console.WriteLine($"Current Good {i} MainIndex is {currentGood.MainIndex} ");

                int currentGoodMainIndex  = currentGood.MainIndex;
                Good currentGoodMainGood = allGoods[currentGoodMainIndex - 1];
                if (currentGoodMainGood.G1 == 0) {
                    //Console.WriteLine($"Current MainGood {currentGoodMainIndex} G1 is {i+1} ");
                    currentGoodMainGood.G1 = i+1;
                } else {
                    //Console.WriteLine($"Current MainGood {currentGoodMainIndex} G2 is {i+1} ");
                    currentGoodMainGood.G2 = i+1;
                }
            }
        }
        Good[] mainGoods = allGoods.Where(g => g != null && g.MainIndex == 0).ToArray();
        int mon10 = (int)(money / 10);
        int [,] dp = new int[mainGoods.Length + 1, mon10 + 1];
        for (int i = 0; i <= mainGoods.Length; i++) {
            for (int j = 0; j <= mon10; j++) {
                if (i==0 || j==0) {
                    dp[i,j] = 0;  // 第一行/列强制为0
                } else {
                    dp[i,j] = -1; // 其他位置初始不可达
                }
            }
        }

        for (int i = 1; i <= mainGoods.Length; i++) {
            Good currentMainGood = mainGoods[i - 1];
            for (int j = 0; j <= mon10; j++) {
                // option1: if no good choosen
                if (dp[i - 1, j] != -1) {
                    dp[i, j] = dp[i - 1, j];
                }

                int sumPrice;
                int sumValue;

                //only main good choosen
                sumPrice = (int)(currentMainGood.Price / 10);
                sumValue = currentMainGood.Value;
                if (j - sumPrice >= 0 && dp[i - 1, j - sumPrice] >= 0) {
                    dp[i, j] = Math.Max(dp[i - 1, j - sumPrice] + sumValue, dp[i - 1, j]);
                }

                if(currentMainGood.G1 != 0){
                    sumPrice = (int)(currentMainGood.Price / 10) + (int)(allGoods[currentMainGood.G1 -1].Price / 10);
                    sumValue = currentMainGood.Value + allGoods[currentMainGood.G1-1].Value;
                    if (j - sumPrice >= 0 && dp[i - 1, j - sumPrice] >= 0) {
                        dp[i, j] = Math.Max(dp[i - 1, j - sumPrice] + sumValue, dp[i, j]);
                    }
                }

                if(currentMainGood.G2 != 0){
                    sumPrice = (int)(currentMainGood.Price / 10) + (int)(allGoods[currentMainGood.G2 -1].Price / 10);
                    sumValue = currentMainGood.Value + allGoods[currentMainGood.G2-1].Value;
                    if (j - sumPrice >= 0 && dp[i - 1, j - sumPrice] >= 0) {
                        dp[i, j] = Math.Max(dp[i - 1, j - sumPrice] + sumValue, dp[i, j]);
                    }
                }

                if(currentMainGood.G1 != 0 && currentMainGood.G2 !=0){
                    sumPrice = (int)(currentMainGood.Price / 10) + (int)(allGoods[currentMainGood.G1 -1].Price / 10) + (int)(allGoods[currentMainGood.G2-1].Price / 10);
                    sumValue = currentMainGood.Value + allGoods[currentMainGood.G1 -1].Value + allGoods[currentMainGood.G2 -1].Value;
                    //Console.WriteLine($"condition sumPrice of {i}{j} is {sumPrice}");
                    //Console.WriteLine($"condition sumValue of {i}{j} is {sumValue}");

                    if (j - sumPrice >= 0 && dp[i - 1, j - sumPrice] >= 0) {
                        dp[i, j] = Math.Max(dp[i - 1, j - sumPrice] + sumValue, dp[i, j]);
                        var test = dp[i, j];
                        //Console.WriteLine($@"{i}{j} is {test}");
                    }
                }
                //Console.WriteLine($"sumPrice of {i}{j} is {sumPrice}");

                //Console.WriteLine($"G1 of {i} is {currentMainGood.G1}, Price is {allGoods[currentMainGood.G1].Price}");
                //Console.WriteLine($"G2 of {i} is {currentMainGood.G2}, Price is {allGoods[currentMainGood.G2].Price}");
                //Console.WriteLine($"sumValue of {i}{j} is {sumValue}");

                //var test = dp[i, j];
                //Console.WriteLine($@"{i}{j} is {test}");
            }
        }

        //var output = dp[2,70];
        //Console.WriteLine($@"2 70 is {output}");

        int result = 0;
        for (int j = 0; j < dp.GetLength(1); j++)
        {
            result = Math.Max(result, dp[dp.GetLength(0) - 1, j]);
        }

        Console.WriteLine(result);
    }
}

public class Good {
    public int Price {
        get;
    }
    public int Value {
        get;
    }
    public int MainIndex {
        get;
    }

    public int G1 {
        get;
        set;
    } = 0;
    public int G2 {
        get;
        set;
    } = 0;

    public Good(int price, int value, int index) {
        Price = price;
        Value = value;
        MainIndex = index;
    }
}