【每日一题】 矩阵取数游戏 题解
矩阵取数游戏
https://ac.nowcoder.com/acm/problem/16645
Description
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:
1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;
2.每次取走的各个元素只能是该元素所在行的行首或行尾;
3.每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值 * ,其中i表示第i次取数(从1开始编号);
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。
Solution
这种题目描述,包含了很多决策状态,肯定是动态规划来做的。由于每一行是独立的,不会相互影响,那么对每一行都取最优决策即可。
我们令 为当前行取[i,j]区间能得到的最优值,显然有递推式
显然有递推式,
对每行做上述dp,通过记忆化搜索保证每个状态只访问一次,这里需要使用高精度,跟zzugzx偷学了一手python
Code
while True: try: n, m = map(int, input().split()); dp = [[0 for i in range(81)] for i in range(81)]; a = [0 for i in range(n + 1)]; def solve(l, r): p = r - l + 1; k = m - p + 1; if dp[l][r] : return dp[l][r]; if l == r : return a[l] * (2 ** k); dp[l][r] = max(solve(l + 1, r) + a[l] * (2 ** k), solve(l, r - 1) + a[r] * (2 ** k)); return dp[l][r]; ans = 0; for i in range(n): dp = [[0 for i in range(100)] for i in range(100)]; a = list(map(int, input().split())); ans += solve(0, m - 1); print(ans); except EOFError: break
Kurisu与牛客的每日一题 文章被收录于专栏
每日一题