CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== 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===
挺基础的_(:з」∠)_
==== 冯宇扬 ====
==== 常程 ====
无

CVBB ACM Team

用户工具

站点工具

页面工具