NC16645矩阵取数游戏

链接：https://ac.nowcoder.com/acm/problem/16645
来源：牛客网

题目描述

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

输入描述:

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

输出描述:

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

思路：

$dp[i][j]$ 表示区间 $i-j$ 的最优解

$dp[i][j]=max(dp[i+1][j]+martix[t][i]*qp(2,m-len+1),dp[i][j-1]+martix[t][j]*qp(2,m-len+1));$

根据状态转移方程可以看出要求得 $dp[i][j]$ 就要先算出 $dp[i+1][j]$ 和 $dp[i][j-1]$

显然要根据区间去算-> $for$ 循环决定顺序

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;


void read(__int128 &x )
{
    x=0;int f=1;char s=getchar();
    for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    x*=f;
}

void print(__int128 x )
{
    if( x<0 ) x=-x,putchar('-');
    if( x>9 ) print(x/10);
    putchar( x%10+'0' );
}
__int128 qp(__int128 a,__int128 b){
    __int128 ans=1;
    while(b){
        if(b&1)ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}

__int128 martix[100][100];
__int128 dp[100][100];

int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            read(martix[i][j]);
        }
    }
    __int128 ans=0;
    for(int t=1;t<=n;++t){
        mem(dp,0);
        for(int len=1;len<=m;++len){
            for(int i=1,j=i+len-1;j<=m;++i,++j){
                dp[i][j]=max(dp[i+1][j]+martix[t][i]*qp(2,m-len+1),dp[i][j-1]+martix[t][j]*qp(2,m-len+1));
            }
        }
        ans+=dp[1][m];
    }
    print(ans);

}