矩阵取数游戏

不能直接1<<j，左移会溢出。所以需要数组记录或者直接快速幂；
想法比较直接，dp[j][k][2]取第j次时，到目前一共取了k次左边的，当前1为取左，0为取右；
正如紫书上说的，变量有几个，设几维；（比较粗暴的方法）

#include<bits/stdc++.h>
using namespace std;
__int128 mp[350][350],n,m,dp[350][350][2],ans;
inline __int128 read(){//快读
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(__int128 x){//__int128输出
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
__int128 power(__int128 a,__int128 b)//快速幂
{
    __int128 res=1;
    while(b)
    {
        if(b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
signed main()
{
    n=read(),m=read();
    for(__int128 i=1;i<=n;i++)
    {
        for(__int128 j=1;j<=m;j++)
        {
            mp[i][j]=read();
        }
    }
    for(__int128 i=1;i<=n;i++)//第i行
    {
        for(__int128 j=1;j<=m;j++)//次数
        {
            for(__int128 k=0;k<=j;k++)//取了k个左端点
            {
                __int128 h=power(2,j);
                if(k>0) dp[j][k][1]=max(dp[j][k][1],max(dp[j-1][k-1][0],dp[j-1][k-1][1])+h*mp[i][k]);
                dp[j][k][0]=max(dp[j][k][0],max(dp[j-1][k][0],dp[j-1][k][1])+h*mp[i][m-j+k+1]);
            }
        }
        __int128 ma1=0;
        for(__int128 k=0;k<=m;k++)
            ma1=max(ma1,max(dp[m][k][1],dp[m][k][0]));
        ans+=ma1;
        memset(dp,0,sizeof(dp));
    }
    print(ans);
}