NC16645 矩阵取数游戏（动态规划）

题目链接

题意：
有一n行m列的矩阵，每次从这n行中取出行首或行尾的数，一个数的权值为 val*2^i，该次得分为这n行取值总和，共取m次，求最大权值和。

题解：
虽然数据较大，但用 int128 完全可以存下。由于取行首或行尾操作容易用转移方程描述，考虑动态规划。
设 pw[i]为对应2的幂，a[i][j]表示i行j列数值， b[i][l][r] 表示第i行左边取了l个数，右边取了r个数的最大得分。
则状态转移方程为 b[i][l][r] = max( b[i][l-1][r]+a[i][l] * pw[l+r]，b[i][l][r-1]+a[i][m-r+1] * pw[l+r] )，对应取第l+r个数时是取行首还是行尾。
结果求出每行最大权值相加就好了。

代码如下：

#include<bits/stdc++.h>
#define ll __int128
#define max(a,b) a>b?a:b
using namespace std;
ll a[85][85],b[85][85][85],pw[85]={1};
int n,m;
template <class t>
inline void in(t &x){
    x=0;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<1)+(x<<3)+(ch&15);
}
inline void print(ll x){
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int main(){
    in(n),in(m);
    for(int i=1;i<=m;++i)pw[i]=pw[i-1]<<1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)in(a[i][j]);    
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            b[i][0][j]=b[i][0][j-1]+a[i][m-j+1]*pw[j];
            b[i][j][0]=b[i][j-1][0]+a[i][j]*pw[j];
            for(int k=1;k<j;++k)
                b[i][k][j-k]=max(b[i][k-1][j-k]+a[i][k]*pw[j],b[i][k][j-k-1]+a[i][m-j+k+1]*pw[j]);
        } 
    ll ans=0;
    for(int i=1;i<=n;++i){
        ll may=0;
        for(int j=0;j<=m;++j)may=max(may,b[i][j][m-j]);
        ans+=may; 
    }
    print(ans);
}