矩阵取数游戏

题目传送门

大致思路

不难发现,每一行取数的结果都是相互独立的,故可以对每行单独处理,将每行的结果进行累加得出答案
那么如何计算每行答案?
记dp[i][j],表示区间[i,j]的分数结果,则状态转移方程为

$$dp[i][j]=max(dp[i+1][j]+val,dp[i][j-1]+val) $$

val为取对应数能获得的分数,我们可以预处理一个2的幂数组,快速得出答案
注意答案可能很大,我们用__int128类型计算

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lll __int128
#define Mio_qh signed
#define el '\n'
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pq priority_queue
const int MOD = 998244353;
const int N = 100721;

int fastpow(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = (base*result)%MOD;
        exp >>= 1;
        base = (base*base)%MOD;
    }
    return result;
}
int hx[8]={1,1,-1,-1,2,-2,2,-2};
int hy[8]={2,-2,2,-2,1,1,-1,-1};

void print(lll x) {  //用于输出
    if(x==0) cout<<0<<el;
    else {
        string ans="";
        while(x!=0) {
            int t=x%10;
            ans=to_string(t)+ans;
            x=x/10;
        }
        cout<<ans<<el;
    }
}

void solve() {
    int n, m;
    cin>>n>>m;
    vector<vector<int> > a(n+1, vector<int>(m+1));
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) cin>>a[i][j];
    }
    vector<lll> power(m+1);
    power[0]=1; power[1]=2;
    for (int i=2;i<=m;i++) power[i]=power[i-1]*2;
    lll ans=0;
    for (int p=1;p<=n;p++) {
        vector<vector<lll>> dp(m+1, vector<lll>(m+1));
        for (int len=1;len<=m;len++) {
            for (int i=1;i+len-1<=m;i++) {
                int j=i+len-1;
                if (len==1) dp[i][j]=a[p][i]*power[m];
                else dp[i][j]=max(dp[i+1][j]+a[p][i]*power[m-len+1],dp[i][j-1]+a[p][j]*power[m-len+1]);
            }
        }
        ans+=dp[1][m];
    }
    print(ans);
}


Mio_qh main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
}