矩阵取数游戏

题意：
给出一个n*m的矩阵，每一次取数从每一行中取一个数，每行取数的得分为每行所取数a[i][j] * ,k表示第几次取，且每次取数只能取头或者尾。求取完后的得分最大值？

思路：
我们可以发现每一行的取数只与当前行有关，所以该题相当于求n次数组中取数得分之和。
我们可以区间dp解决。每一次不断增加区间长度，区间长度为1时相当于该数为最后一个取得。
状态转化方程：
dp[i][j]=max(dp[i+1][j]+(a[i]<<(j-i+1),dp[i][j-1]+(a[j]<<(j-i+1)));
结果将每一行的dp[1][m]加起来就好。

注意：对于数据范围最好用__int128,否则只能用高精度了。

代码：

#include <bits/stdc++.h>
#define inf 99824435300000
using namespace std;

typedef long long ll;

inline __int128 read()
{
    __int128 x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        {
            f=-f;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f*x;
}

inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

struct w
{
    ll x, y;
} w, w2;

__int128 a[105], dp[105][105], sum=0;

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=m;j++)
        {
            a[j]=read();
            dp[j][j]=a[j]<<m;
        }
        for(int k=2;k<=m;k++)
        {
            for(int j=1;j+k-1<=m;j++)
            {
                    dp[j][j+k-1]=max(dp[j][j+k-2]+(a[j+k-1]<<(m-k+1)),dp[j+1][j+k-1]+(a[j]<<(m-k+1)));
            }
        }
        sum+=dp[1][m];
    }
    write(sum);
    return 0;
}