题目描述

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 * 2i，其中i表示第i次取数（从1开始编号）；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入描述:

第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。

输出描述:

输出一个整数，即输入矩阵取数后的最大得分。

题解

取数游戏2的高配版
对于每一行，我们所做出的抉择就是是选行首的还是行尾的。我们可以设置dp[i][j]表示剩下的区间是从i到j的，也就是我们选了1~i-1和j+1到n。那么很明显，对于第k次选择，dp[i][j]=max(dp[i-1][j]+a[k][i]2^k,dp[i][j+1]+a[k][j]2^k)。
要注意的是这道题爆long long，我直接用__int128加手写输出函数搞的，没有用高精

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
long long a[105][105];
__int128_t dp[105][105];
////////////////////////////////////////////////////////////////////////
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin>>a[i][j];
    __int128_t ans=0,sign=1,sum=0;
    for(int cnt=1;cnt<=n;++cnt){
        for(int i=1;i<=m;++i){
            sign*=2;
            for(int j=0;j<=i;++j){
                dp[j][n-i+j+1]=0;
                if(!j)dp[j][m-i+j+1]=dp[j][m-i+j+2]+a[cnt][m-i+j+1]*sign;
                else if(i==j)dp[j][m-i+j+1]=dp[j-1][m-i+j+1]+a[cnt][j]*sign;
                else dp[j][m-i+j+1]=max(dp[j][m-i+j+2]+a[cnt][m-i+j+1]*sign,dp[j-1][m-i+j+1]+a[cnt][j]*sign);
                sum=max(sum,dp[j][m-i+j+1]);
                //cout<<j<<" "<<n-i+j+1<<" "<<dp[j][n-i+j+1]<<endl;
            }
        }
        //cout<<sum<<endl;
        ans+=sum;sum=0,sign=1;
    }
    ans+=sum;
    print(ans),putchar(10);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/