NOIP真题：矩阵取数问题

憨题，除了要写高精度，分行考虑，直接区间dp

60pts:

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define maxn 106
#define int long long 
#define lson t[s].lc
#define rson t[s].rc
#define rep(i,a,b) for (int i=(a);i<=(b);++i)
#define dep(i,a,b) for (int i=(a);i>=(b);i--)
#define erep(i,a) for (int i=head[(a)];i!=-1;i=e[i].next)
int val[maxn][maxn],dp[maxn][maxn][maxn],n,m;
inline int dfs(int pan,int now,int l,int r)
{
	if (l==r) 
	{
		int tmp=(1<<now);
		int cur=val[pan][l]*tmp;
		return cur;
	}
	if (~dp[now][l][r]) return dp[now][l][r];
	int tmp=0;
	int lmx=(1<<now);
	int rmx=lmx;
	lmx*=val[pan][l],rmx*=val[pan][r];
	tmp=max(lmx+dfs(pan,now+1,l+1,r),rmx+dfs(pan,now+1,l,r-1));
	return dp[now][l][r]=tmp;
}
signed main()
{	
	cin>>n>>m;
	rep(i,1,n) rep(j,1,m) scanf("%lld",&val[i][j]);
	int ans=0;
	rep(i,1,n)
	{
		memset(dp,-1,sizeof(dp));
		ans+=dfs(i,1,1,m);
	}
	cout<<ans;
}