矩阵取数游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1344 字

n×m矩阵，每行每次取行首或行尾，第i次取数

一本通
练习

正文

/*
原题：矩阵取数游戏（NOIP2007，每行独立区间 DP，乘 2 的幂）
题意：n×m 矩阵，每行每次取行首或行尾，第 i 次取数乘 2^i，求所有行最大总分。
思路：每行独立：dp[l][r] 为区间 [l,r] 剩余时的最大得分，
      dp[l][r]=max{a[l]*2^(m-len+1)+dp[l+1][r], a[r]*2^(m-len+1)+dp[l][r-1]}。
复杂度：时间 O(n*m^2)，空间 O(m)
易错点：每行独立求和；分数与 2^m 会超过 64 位，必须用 __int128；注意 2 的幂次。
*/
#include <bits/stdc++.h>
using namespace std;
void print128(__int128 x){
    if(x==0){cout<<0;return;}
    string s;
    while(x){
        s+=char('0'+(int)(x%10));
        x/=10;
    }
    reverse(s.begin(),s.end());
    cout<<s;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<__int128> pow2(m+2);
    pow2[0]=1;
    for(int i=1;i<=m+1;i++) pow2[i]=pow2[i-1]*2;
    __int128 total=0;
    for(int row=0;row<n;row++){
        vector<long long> a(m+1);
        for(int i=1;i<=m;i++) cin>>a[i];
        vector<vector<__int128>> dp(m+1, vector<__int128>(m+1,0));
        for(int i=1;i<=m;i++) dp[i][i]=a[i]*pow2[m];
        for(int len=2;len<=m;len++){
            for(int l=1;l+len-1<=m;l++){
                int r=l+len-1;
                int step=m-len+1;
                __int128 v1=a[l]*pow2[step]+dp[l+1][r];
                __int128 v2=a[r]*pow2[step]+dp[l][r-1];
                dp[l][r]=max(v1,v2);
            }
        }
        total+=dp[1][m];
    }
    print128(total);
    cout<<"\n";
    return 0;
}

矩阵取数游戏

正文

一本通·提高篇的其它内容