P1005 矩阵取数游戏
斯德哥尔摩
2018-10-22 23:52:16
[P1005 矩阵取数游戏](https://www.luogu.org/problemnew/show/P1005)
首先发现每一行怎么选对于其他的行没有任何影响。
那就单独把每一行提出来，开始区间$DP$。
设$dp[i][j]$代表取区间$[i,j]$的最大值，$val[i]$为当前行的每个数。
然后我们考虑，对于每一个新的$dp[i][j]$，有两种情况：
1. 先取前面的$val[i]$，再取剩下的$dp[i+1][j]$即$[i+1,j]$的最大值：
$$dp[i][j]=2\times dp[i+1][j]+2\times val[i]$$
即：把接下来取的所有数乘上$2$，也就是把接下来取的所有数从$x\times 2^{i}$变为$x\times 2^{i+1}$。
即：每次取都把之前的翻一倍，然后当前取的值$val[i]$要乘上$2$。
2. 先取后面的$val[j]$，再取剩下的$dp[i][j-1]$即$[i,j-1]$的最大值，同理：
$$dp[i][j]=2\times dp[i][j-1]+2\times val[j]$$
到此，方程推完了：
$$dp[i][j]=\max\left\{\begin{array}{}2\times dp[i+1][j]+2\times val[i]\\2\times dp[i][j-1]+2\times val[j]\end{array}\right.$$
然而，这个题的最终答案炒鸡大——炸$long\ long$。。。
于是，高精？
对我来说是$\tan(\frac{\pi}{2}+k\pi),k\in Z$。。。
而且据说高精写的丑会$TLE$。。。
怎么办？
$\underline\ \ \underline\ int128$！
这玩意好啊！
然后就没了。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 85
using namespace std;
int n,m;
__int128 ans=0;
__int128 val[MAXN][MAXN],dp[MAXN][MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void write(__int128 x){
if(x>9)write(x/10);
putchar(x%10+'0');
}
__int128 solve(int x){
memset(dp,0,sizeof(dp));
for(int i=0;i<=m;i++)
for(int j=1;j+i<=m;j++)
dp[j][j+i]=max(dp[j+1][j+i]*2+val[x][j]*2,dp[j][j+i-1]*2+val[x][j+i]*2);
return dp[1][m];
}
void work(){
for(int i=1;i<=n;i++)ans+=solve(i);
write(ans);putchar('\n');
}
void init(){
n=read();m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
val[i][j]=read();
}
int main(){
init();
work();
return 0;
}
```