洛谷P1005 矩阵取数游戏

题目描述

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：

1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；

2.每次取走的各个元素只能是该元素所在行的行首或行尾；

3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编号）；

4.游戏结束总得分为m次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入输出格式

输入格式：

输入文件game.in包括n+1行：

第1行为两个用空格隔开的整数n和m。

第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。

数据范围：

60%的数据满足：1<=n, m<=30，答案不超过10^16

100%的数据满足：1<=n, m<=80，0<=aij<=1000

输出格式：

输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大得分。

输入输出样例

输入样例#1：

2 3
1 2 3
3 4 2

输出样例#1：

说明

NOIP 2007 提高第三题

又一道为数不多自己想出来的dp，dp入门指日可待了233。

从整体上来看，这道题的状态不好表示，转移也很麻烦。但是我们从局部来看：整个大问题其实是由若干个小问题组成的。更直接一点说，每一行的取数是分开的，只要求出每一行的答案相加起来就是最后的结果。

那么我们来考虑每一行的这个dp。我们可以用dp[a][b]表示取a~b这个区间的数最优的策略。那么很明显dp[i][i] = 第i个数的值。初状态就设置好了。因为有两种可能性，一种是取左边，一种是取右边，状态转移方程也就简单的写了出来：dp[j][j + i] = max(dp[j][i + j - 1] * 2 + dp[i + j][i + j], dp[j + 1][i + j] * 2 + dp[j][j])。

虽然说题目本身不难，但是一看数据范围就恶心了。这是明摆着的让你写高精度啊……不过我们偏不写高精度，这类问题可以用WKL大神在基础语法课上提到的“伪高精度”解决。也就是用两个longlong拼成一个大整数，前16位后16位。至此整个问题得到了完美的解决。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 85;
const long long dc = 1e16;
struct exLL{
	long long a, b;
	exLL operator *(int d) const {
		return (exLL){a * d + b * d / dc, b * d % dc};
	}
	exLL operator +(exLL d) const {
		return (exLL){a + d.a + (b + d.b) / dc, (b + d.b) % dc};
	}
};
bool operator <(exLL a, exLL d) {
	if(d.a != a.a) return a.a < d.a;
	else return a.b < d.b;
}
exLL dp[maxn][maxn], ans, sol1, sol2;
int n, m;

int main() {
	scanf("%d%d", &n, &m);
	for(register int k = 1; k <= n; ++k) {
		memset(dp, 0, sizeof(dp));
		for(register int j = 1; j <= m; ++j) 
			scanf("%lld", &dp[j][j].b);
		for(register int i = 1; i < m; ++i) 
			for(register int j = 1; j <= m - i; ++j) {
				sol1 = dp[j][i + j - 1] * 2 + dp[i + j][i + j];
				sol2 = dp[j + 1][i + j] * 2 + dp[j][j];
				dp[j][i + j] = max(sol1, sol2);
			}
		ans = ans + dp[1][m] * 2;
	}
	if(ans.a) printf("%lld", ans.a);
	printf("%lld", ans.b);
	return 0;
}

Rockdu's Blog