{"problem":{"name":"「AWOI Round 2 D」数字三角形","description":{"content":"Glad 发现了一个 $n$ 层数字三角形，他发现可以用魔法来操纵这个三角形！ 他可以先消耗 $nk_1$ 点消耗值，让将三角形旋转 $k_1$ 次。其中“旋转”指绕三角形中心顺时针旋转 $120^\\circ$。 然后，他可以不停地进行下面操作： - 消耗 $1$ 点消耗值，选择一层，调换这一层任意两个数的位置。 现在，Glad 要从三角形的最后一层走到最顶层，起点可以为最后一层的任意一个","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9541"},"statements":[{"statement_type":"Markdown","content":"Glad 发现了一个 $n$ 层数字三角形，他发现可以用魔法来操纵这个三角形！\n\n他可以先消耗 $nk_1$ 点消耗值，让将三角形旋转 $k_1$ 次。其中“旋转”指绕三角形中心顺时针旋转 $120^\\circ$。\n\n然后，他可以不停地进行下面操作：\n\n- 消耗 $1$ 点消耗值，选择一层，调换这一层任意两个数的位置。\n\n现在，Glad 要从三角形的最后一层走到最顶层，起点可以为最后一层的任意一个数，行走的每一步只能走到与当前数相邻的数上，且每一行只能经过一个数。\n\nGlad 想在经过数之和最大的前提下让消耗的消耗值最小，你可以帮帮他吗？\n\n## Input\n\n一个正整数 $n$，表示三角形的层数。\n\n后面 $n$ 行，表示数字三角形。其中第 $i$ 层有 $i$ 个数（$1\\leqslant i\\leqslant n$）。\n\n## Output\n\n两个整数，分别表示最大能经过的数之和以及最少要消耗多少消耗值。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n初始三角形为：\n\n```\n    1\n   2 3\n  4 5 6\n10 9 8 7\n2 5 2 5 6\n```\n\n将其向右翻转 $2$ 次，消耗 $10$ 点调换值，此时三角形变为：\n\n```\n    6\n   7 5\n  6 8 2\n 3 5 9 5\n1 2 4 10 2\n```\n\n无须调换数字，沿着 $6,7,8,9,10$ 走，可以得到最大值 $40$，共耗费 $10$ 点调换值。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 数据范围 | 特殊性质 | 分值 |  \n| :-----------: | :-----------: | :-----------: | :-----------: |  \n| $\\text{Subtask1}$ | $1\\leqslant n\\leqslant 10$ | AB | $10$ |  \n| $\\text{Subtask2}$ | $1\\leqslant n \\leqslant 10$ | A | $10$ |  \n| $\\text{Subtask3}$ | $1\\leqslant n \\leqslant 10$ | B | $10$ |  \n| $\\text{Subtask4}$ | $1\\leqslant n \\leqslant 10$ | 无 | $10$ | \n| $\\text{Subtask5}$ | $1\\leqslant n \\leqslant 40$ | 无 | $20$ | \n| $\\text{Subtask6}$ | $1\\leqslant n\\leqslant 10^3$ | 无 | $40$ |  \n\n特殊性质 A：不需要调换数字就可以得到最优解。\n\n特殊性质 B：不需要向右旋转就可以得到最优解。\n\n对于 $100\\%$ 的数据，保证：$1\\leqslant n\\leqslant 10^3$，$0\\leqslant a_i\\leqslant10^4$。\n\n**【工作人员】**\n\n| $\\text{Idea}$ | $\\text{Data}$ | $\\text{Check}$ | $\\text{Solution}$ |\n| :----------: | :----------: | :----------: | :----------: |\n|[S__X](/user/310466) |[S__X](/user/310466)|[I_am_AKed_by_NOI](/user/807853) | [I_am_AKed_by_NOI](/user/807853) |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9541","tags":["动态规划 DP"],"sample_group":[["5\n1\n2 3\n4 5 6\n10 9 8 7\n2 5 2 5 6","40 10"]],"created_at":"2026-03-03 11:09:25"}}