Warning: session_start(): open(/tmp/sess_c3e1a799484f7b687a4e7d5b3ac17625, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020/08/29--2020/09/04======
----
===== 团队训练 =====
暂无
----
===== 王瑞琦 =====
===比赛===
无
===专题===
无
===== 冯宇扬 =====
===比赛===
===专题===
===== 常程 =====
本周摸了，由于假期小作业（由于我写得太慢
===比赛===
无
===专题===
无
===== 本周推荐 =====
==== 王瑞琦 ====
一道简单的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===
挺基础的_(:з」∠)_
==== 冯宇扬 ====
==== 常程 ====
无