洛谷P1005 矩阵取数游戏

题目描述帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n×mn \times mn×m的矩阵，矩阵中的每个元素ai,ja_{i,j}ai,j​均为非负整数。游戏规则如下：每次取数时须从每行各取走一个元素，共nnn个。经过mmm次后取完矩阵内所有元素；每次取走的各个元素只能是该元素所在行的行首或行尾；每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值×2i\times 2^i×2i，其中iii表示第iii次取数（从111开始编号）；游戏结束总得分为mmm次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。输入格式输入文件包括n+1n+1n+1行：第111行为两个用空格隔开的整数nnn和mmm。第2∽n+12\backsim n+12∽n+1行为n×mn \times mn×m矩阵，其中每行有mmm个用单个空格隔开的非负整数。输出格式输出文件仅包含111行，为一个整数，即输入矩阵取数后的最大得分。输入输出样例输入 #1 复制 2 3
1 2 3
3 4 2
输出 #1 复制 82说明/提示NOIP 2007 提高第三题数据范围：60%的数据满足：1≤n,m≤301\le n, m \le 301≤n,m≤30，答案不超过101610^{16}1016
100%的数据满足：1≤n,m≤801\le n, m \le 801≤n,m≤80，0≤ai,j≤10000 \le a_{i,j} \le 10000≤ai,j​≤1000
分析题目
不难发现，每行取的数，都是自己玩自己的，
考虑区间Dp
f[i][j]表示从i取到j的最优答案

#include <cstdio>
#include <iostream>
#include <cstring>
#define int __int128
using namespace std;
int n,m,jv[85][85],ans;
int f[85][85];
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   ch=getchar();if(ch=='-')f=-1;}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int solve(int hang){
   
	memset(f,0,sizeof(f));
	for(int les=0;les<=m;les++){
   //les 什么鬼？？。。 
		for(int rar=1;les+rar<=m;rar++){
   
			f[rar][rar+les]=max(2*f[rar+1][rar+les]+2*jv[hang][rar],2*f[rar][rar+les-1]+2*jv[hang][rar+les]);
		} 
	}
	return f[1][m];
}
inline void output(__int128 x){
   
    if(x>9)
        output(x/10);
    putchar(x%10+'0');
}
main(){
   
	n=read();m=read();
	for(int i=1;i<=n;i++){
   
		for(int j=1;j<=m;j++){
   
			jv[i][j]=read();
		}
	}
	for(int i=1;i<=n;i++) ans+=solve(i);//似乎每行与每行之间没有鸡毛关系，所以一行一行搞 
    output(ans);
	return 0;
}