【每日一题】7月9日 矩阵取数游戏

类似题目：https://ac.nowcoder.com/acm/problem/14701 取数游戏
题意： 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * ，其中 表示第 次取数（从1开始编号）。并且每次取走的各个元素只能是该元素所在行的行首或行尾。
一共取 次，问每行取数的最大得分和是多少。

分析：
每行取数互不影响，所以我们依次计算每行的最大取数方案累加起来即可。

• 和 的范围不大，我们可以定义 表示该行左边取数取到 位置，右边取数取到 位置的最大得分。进行dfs记忆化搜索答案。
• 注意数据范围爆long long,用__int128才能过.

#include<bits/stdc++.h>
using namespace std;

using namespace std;

const int maxn=1e5+10;
typedef __int128 ll;

void read(ll &x )
{
    x=0;int f=1;char s=getchar();
    for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    x*=f; 
}

void print( ll x )
{
    if( x<0 ) x=-x,putchar('-');
    if( x>9 ) print(x/10);
    putchar( x%10+'0' );
}

ll n,m,a[88];
ll dp[88][88];

ll dfs( int l,int r )
{
    if( l>r ) return 0;
    if( dp[l][r] ) return dp[l][r];
    int num=l-1+m-r;
    ll res1=((ll)1<<num)*a[l]+dfs(l+1,r);
    ll res2=((ll)1<<num)*a[r]+dfs(l,r-1);
    return dp[l][r]=max(res1,res2);
}


int main()
{
    read(n);read(m);
    ll ans=0;
    for( int i=1;i<=n;i++ )
    {
        for( int j=1;j<=m;j++ ) read(a[j]);
        memset(dp,0,sizeof(dp));
        ans+=dfs(1,m);
    }
    print(ans);
}