acwing::acwing3445 命名空间参考

1. 点菜问题

更多...

类
struct	status

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing3445, case1)
	TEST (acwing3445, case2)

详细描述

1. 点菜问题

函数说明

main()

int acwing::acwing3445::main	(	istream &	cin,
		ostream &	cout )

在文件 acwing408.cpp 第 1839 行定义.

                                              {
            int c, n;
            cin >> c >> n;
            vector<int> p = vector<int>(n);
            vector<int> v = vector<int>(n);
            for(int i = 0; i < n; i++) {
                cin >> p[i] >> v[i];
            }
            vector<status> dp = vector<status>(c + 1, status{
                                                              .v    = 0,
                                                              .free = vector<bool>(n, true)});
            int max_v         = 0;
            for(int i = 0; i <= c; i++) {
                for(int j = 0; j < n; j++) {
                    max_v = max(max_v, dp[i].v);
                    if(dp[i].free[j]) {
                        int next_v = dp[i].v + v[j];
                        int next_c = i + p[j];
                        if(next_c <= c && next_v > dp[next_c].v) {
                            dp[next_c].v       = next_v;
                            dp[next_c].free    = vector<bool>(dp[i].free);
                            dp[next_c].free[j] = false;
                        }
                    }
                }
            }
            cout << max(max_v, dp[c].v);
            return 0;
        }

被这些函数引用 TEST() , 以及 TEST().

TEST() [1/2]

acwing::acwing3445::TEST	(	acwing3445	,
		case1	)

在文件 acwing408_test.cpp 第 2007 行定义.

                                {
            istringstream in("90 4\n"
                             "20 25\n"
                             "30 20\n"
                             "40 50\n"
                             "10 18");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("95", ans);
        }

引用了 main().

TEST() [2/2]

acwing::acwing3445::TEST	(	acwing3445	,
		case2	)

在文件 acwing408_test.cpp 第 2019 行定义.

                                {
            istringstream in("300 20\n"
                             "19 24\n"
                             "26 3\n"
                             "2 5\n"
                             "17 8\n"
                             "13 17\n"
                             "10 9\n"
                             "19 9\n"
                             "30 4\n"
                             "23 24\n"
                             "9 9\n"
                             "5 22\n"
                             "10 15\n"
                             "9 10\n"
                             "15 29\n"
                             "20 14\n"
                             "8 12\n"
                             "4 23\n"
                             "24 22\n"
                             "16 13\n"
                             "5 26");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("298", ans);
        }

引用了 main().