这真是一道有趣的题目。 ——垃圾一个
首先,我们知道,有一个
C++11才有的东西:__int128,它的上界是(2^{128}-1)。
然后,我们知道,有一个叫宏定义的东西,它可以长这样#define int __int128。
最后,有一个玄学知识,main函数不仅可以是int,也可以是signed。
基础玄学知识介绍完毕。
接下来说说如何(DP)。
首先我们仅考虑每一行如何取(具体原因自行看题)。
然后对于每一行,我们仅考虑取头与取尾的(max)值(具体原因同上)。
然后定义(f_{i,j})为取区间([i,j])的最大值,定义(a_i)为该行第(i)个数。
则转移方程为:
(f_{i,j}=max{f_{i+1,j}+a_i imes x,f_{i,j-1}+a_j imes x},x)为题目说的要加的数。
接下来考虑如何降维打击。
你想,如果取的时候先乘上一个2,然后每次遇到一个区间时在乘2,最后效果其实是一样的。
所以(DP)式变成:
(f_{i,j}=max{2 imes f_{i+1,j}+2 imes a_i,2 imes f_{i,j-1}+2 imes a_j})
化简为:
(f_{i,j}=max{2 imes (f_{i+1,j}+a_i),2 imes (f_{i,j-1}+a_j)})
即核心代码为
int dp(int sum[])
{
memset(f,0,sizeof(f));
int i,j;
for(i=0;i<=m;i++) //i枚举长度,注意,长度可以为0。
for(j=1;i+j<=m;j++) //j枚举起点。
f[j][i+j]=max(2*(f[j+1][i+j]+sum[j]),2*(f[j][i+j-1]+sum[i+j]));
return f[1][m]; //最后所求区间为f[1][m]。
}
然后使用我们的基础玄学知识。
果断CE,没猜错吧?
__int128不自带输入输出!!!
这里提供快读快写的板子。
最后放个总代码。
#include<bits/stdc++.h>
using namespace std;
#define int __int128
int a[90][90];
int f[90][90];
int n,m;
template<typename T>void qin(T &x)
{
x=0;
char ch;bool f=0;
ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),f=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(f==1) x=-x;
}
void qout(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) qout(x/10);
putchar(x%10+'0');
}
int dp(int sum[])
{
memset(f,0,sizeof(f));
int i,j;
for(i=1;i<=m;i++)
for(j=1;i+j<=m;j++)
f[j][i+j]=max(2*(f[j+1][i+j]+sum[j]),2*(f[j][i+j-1]+sum[i+j]));
return f[1][m];
}
int main()
{
qin(n),qin(m);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
qin(a[i][j]);
int ans=0;
for(i=1;i<=n;i++)
ans+=dp(a[i]);
qout(ans);
return 0;
}