2020-2021:teams:no_morning_training:weekly:week14
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:weekly:week14 [2020/09/02 22:20] nomansland 创建 |
2020-2021:teams:no_morning_training:weekly:week14 [2020/09/03 00:39] (当前版本) shaco |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| ===专题=== | ===专题=== | ||
| ===== 常程 ===== | ===== 常程 ===== | ||
| + | 本周摸了，由于假期小作业（由于我写得太慢 | ||
| ===比赛=== | ===比赛=== | ||
| + | 无 | ||
| ===专题=== | ===专题=== | ||
| + | 无 | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ==== 王瑞琦 ==== | ==== 王瑞琦 ==== | ||
| + | 一道简单的dp题。 | ||
| + | ===来源=== | ||
| + | 洛谷P1005:[[https://www.luogu.com.cn/problem/P1005|矩阵取数游戏]] | ||
| + | ===标签=== | ||
| + | dp，高精度 | ||
| + | ===题意=== | ||
| + | 在一个矩阵中取数，每次在n行中各取一个，只能取行首或者行尾。每次取数的得分为“取的数值*2^i”（i为第i次取数）。求一个取数方案使得得分之和最大。 | ||
| + | ===题解=== | ||
| + | 由题意可知每行的取数是独立的，即我们只要分别处理每行的取数操作。\\ | ||
| + | 显然每次取数操作之间有先后关联，而取一次数的得分与其先前的所有操作密切相关，因此自然得出是dp。\\ | ||
| + | 令f(i,j)表示一行还剩第i至第j个数时得分的最大值，它的前状态为f(i-1,j)与f(i,j+1)，于是可以得到状态转移方程：\\ | ||
| + | f(i,j)=max{f[i-1,j]+a[i-1]*2^(m-j+i-1),f[i,j+1]+a[j+1]*2^(m-j+i-1)}\\ | ||
| + | 由于答案没有取模，需要再用到高精度。 | ||
| + | ===comment=== | ||
| + | 挺基础的_(:з」∠)_ | ||
| ==== 冯宇扬 ==== | ==== 冯宇扬 ==== | ||
| ==== 常程 ==== | ==== 常程 ==== | ||
| + | 无 | ||
2020-2021/teams/no_morning_training/weekly/week14.1599056420.txt.gz · 最后更改: 2020/09/02 22:20 由 nomansland
