斯德哥尔摩 的博客

斯德哥尔摩 的博客

P1005 矩阵取数游戏

posted on 2018-10-22 23:52:16 | under 刷题 |

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$!

这玩意好啊!

然后就没了。。。

附代码:

#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;
}