每日一题 矩阵取数游戏 (区间dp)

一.题意

n*m 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * 2 ^ i ，i 为第 i 次取数且每次取走的各个元素只能是该元素所在行的行首或行尾，取 m 次，求取数的最大得分和。

二.题解

因为每次只能取行首或者行尾，所以每行取得顺序都是独立的。
由此可以从 求最大的得分和 转换成 求每行的最大得分和。
如何求每行的最大得分和?
可以发现肯定是从一个长度为 1 的区间扩展到 长度为 n 的区间。
所以我们可以用区间 dp 来求解。
设 dp[l][r] 来维护 l ~ r 区间的最大得分。
转移方程:
这里的 x 为第几次取数。
这题还要注意数据会爆longlong ， 所以必须祭出 __int128 或者用大数。

三.代码:

#include<bits/stdc++.h>
#define pb push_back
#define ld long double
//#define ll long long
#define ll __int128
#define ull unsigned long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define endl "\n"
#define pi acos(-1.0)
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int manx=1e6+5;
const int N=100+5;
const int mod=1e9+7;
const int mo=1e8;
ll read()
{
    ll 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(ll x)
{
    if(x < 0) {putchar('-');x = -x;}
    if(x/10) print(x/10);
    putchar(x%10+'0');
}

ll dp[N][N],a[N];
ll n,m;
ll ans=0;

ll dfs(ll l,ll r){
    ll x=((ll)1<< (m-r+l));
    if(dp[l][r]) return dp[l][r];
    if(l==r) return a[l] * x;
    dp[l][r]=max(dfs(l+1,r)+a[l]*x, dfs(l,r-1)+a[r]*x);
    return dp[l][r];
}

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