刷题记录:牛客NC16645[NOIP2007]矩阵取数游戏

传送门:牛客

题目描述:

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 * 2i，其中i表示第i次取数（从1开始编号）；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入:
2 3
1 2 3
3 4 2
输出:
82
1
2
3
4
5
6
7
8
9
10
11
12

emmm感觉这道题的难度主要集中在高精度(观察范围显然需要高精),假设没有高精度的话这道题就退化成这道题

主要思路:

1. 对于我们的二维矩阵取数显然我们可以将其拆分成一维数列的各自得分之和,然后再相加.对于一维数列的取数如何获得最大得分的$dp思想以及转移方程$和这道题一模一样,此处就不再赘述了(当然也可以不用那道题的方法,然后使用维护左右端点的dp方法,下面代码中就使用了不同的维护的方法)
2. 对于我们的高精方面,这个显然是比较难以维护的,但是我现在又不是在打OI.ACM可是能带纸质资料的,所以对于高精能水就水了,巧了,这道题竟然能使用__int128水过,那为什么不水呢
3. 但是对于__int128来说,我们并没有直接输出的函数,所以我们需要手打输出函数

void print(ll num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
1
2
3
4
5
6

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll __int128
//typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
void print(ll num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
ll a[100];
ll dp[100][100];
ll max(ll aa,ll bb){return aa>bb?aa:bb;}
ll qpow(ll aa) {
	ll b=1;
	for(int i=1;i<=aa;i++) {
		b*=2;
	}
	return b;
}
int main() {
	int n,m;
	n=read();m=read();ll ans=0;
	while(n--) {//进行n层循环
		ll maxx=0;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=m;i++) a[i]=read();
		for(int i=1;i<=m;i++) {
			for(int j=m;j>=i;j--) {
				dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i-1]*qpow(i-1+m-j));
				dp[i][j]=max(dp[i][j],dp[i][j+1]+a[j+1]*qpow(i-1+m-j));
			}
		}
		for(int i=1;i<=m;i++) {//使用端点枚举的话最后会剩下一个数字没有被取,假设是长度的话就不需要再枚举一遍了
			maxx=max(maxx,dp[i][i]+a[i]*qpow(m));
		}
		ans+=maxx;
	}
	if(ans) {
		print(ans);
	}else {
		putchar(48);//48就是字符0 
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68