矩阵取数游戏

题意

一个的矩阵，每次每行取一个数，取次。

每行取数的得分 被取走的元素值 。

求得分的最大值。

分析

显然每行怎么取值都是相互独立的，不会影响其他行，所以我们只需要考虑如何取值才可以让一行的得分最大化。

很明显，我们最先只可以取第一个或者最后一个数，第二次取剩下的第一个或者最后一个数。

我们可以利用区间dp记忆化来做这题。

注意会爆

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int __int128_t
const int inf = 0x3f3f3f3f;
const int maxn = 85;
const int M = 1e9+7;
int n,m,k,ok;

int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return f*x;
}

void print(int x)
{
    if(x < 0) {putchar('-');x = -x;}
    if(x/10) print(x/10);
    putchar(x%10+'0');
}

int a[maxn],b[maxn];

int dp[maxn][maxn][maxn];

int dfs(int l,int r,int cs)         //[l,r]区间取第cs个数
{   
    if(cs > m) return 0;
    if(dp[l][r][cs]) return dp[l][r][cs];
    int ans1 = b[cs]*a[l] + dfs(l+1,r,cs+1);        //取第一个数
    int ans2 = b[cs]*a[r] + dfs(l,r-1,cs+1);        //取最后一个数
    return dp[l][r][cs] = max(ans1,ans2);           //记忆化
}

signed main()
{
    n = read(),m = read();
    int ans = 0;
    b[1] = 2;
    for(int i = 2; i <= m; i++) 
    {
        b[i] = b[i-1]*2;
    }
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {
            a[j] = read();
        }
        mem(dp,0);
        ans += dfs(1,m,1);
    }
    print(ans);
    return 0;
}