{"problem":{"name":"[BCSP-X 2024 6 月小学高年级组] 学习计划","description":{"content":"暑假共有 $n$ 天，第 $i$ 天的精力指数为 $a[i]$，你想要利用假期**依次（按 $1, 2, \\ldots, m$ 顺序）** 复习 $m$ 门功课，第 $i$ 门功课的重要程度为 $b[i]$，且**每门功课的复习时段必须连续，并且不能有某天不干事。** 假设第 $i$ 门功课的复习时段为第 $l \\sim r$ 天，那么第 $i$ 门功课的收益为 $b[i] \\times (a[","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4172"},"statements":[{"statement_type":"Markdown","content":"暑假共有 $n$ 天，第 $i$ 天的精力指数为 $a[i]$，你想要利用假期**依次（按 $1, 2, \\ldots, m$ 顺序）** 复习 $m$ 门功课，第 $i$ 门功课的重要程度为 $b[i]$，且**每门功课的复习时段必须连续，并且不能有某天不干事。**\n\n假设第 $i$ 门功课的复习时段为第 $l \\sim r$ 天，那么第 $i$ 门功课的收益为 $b[i] \\times (a[l] + a[l + 1] + \\ldots + a[r])$，你的总收益为 $m$ 门功课收益的总和。\n\n请你制订一个复习计划，使得总收益最大。\n\n形式化地，给定序列 $a[1 \\sim n], b[1 \\sim m]$，你需要把 $1, 2, \\ldots, n$ 这个序列分成首尾相连且非空的 $m$ 段，假设每段的 $a$ 之和为 $s[1 \\sim m]$，最大化 $\\sum_{i=1}^{m} b[i] \\times s[i]$ 的值。\n\n例如 $a = [-3, 6, -1, -8, 7, -6], b = [-3, 2]$，最优策略是第 $1 \\sim 4$ 天复习第 $1$ 门功课，收益为 $-3 \\times (-3 + 6 - 1 - 8) = 18$；第 $5 \\sim 6$ 天复习第 $2$ 门功课，收益为 $2 \\times (7 - 6) = 2$；总收益为 $18 + 2 = 20$。\n\n例如 $a = [6, 3, 5, 10, 5], b = [-8, -5, -5]$，最优策略是分成 $[1], [2, 3, 4], [5]$ 三段，总收益为 $-8 \\times 6 - 5 \\times (3 + 5 + 10) - 5 \\times 5 = -163$。\n\n## Input\n\n第一行 1 个整数 $T$，代表有 $T$ 组数据。\n\n每组数据第一行 2 个整数 $n, m$，第二行 $n$ 个整数 $a[1 \\sim n]$，第三行 $m$ 个整数 $b[1 \\sim m]$。\n\n## Output\n\n输出 $T$ 行，每行 1 个整数代表答案。\n\n[samples]\n\n## Note\n\n对于所有数据，满足 $1 \\leq T \\leq 20, 1 \\leq m \\leq n \\leq 2000, -10^3 \\leq a[i], b[i] \\leq 10^3$。\n\n- 对于测试点 1~7：$n \\leq 10$；\n- 对于测试点 8~12：$n \\leq 500$；\n- 对于测试点 13~16：所有 $a[i], b[i]$ 为正整数；\n- 对于测试点 17~20：$n \\leq 2000$；","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4172","tags":["动态规划 DP","2024","北京","BCSP-X"],"sample_group":[["5\n6 2\n-3 6 -1 -8 7 -6\n-3 2\n5 4\n-9 -6 -6 -7 -8\n-5 7 -9 -3\n7 7\n7 2 3 0 -2 4 2\n-9 -2 -5 0 -7 9 -1\n5 3\n10 4 6 7 4\n-1 -9 2\n5 3\n6 3 5 10 5\n-8 -5 -5","20\n144\n-34\n-12\n-163"]],"created_at":"2026-03-03 11:09:25"}}