矩阵取数游戏

题目大意：
给定一个n*m的矩阵，每次从每行最右或最左端取一个数，每取走一个数会有一个得分，求最大得分。

思路：
根据题目可知，取数时每行互不影响，所以可以将其分开一行一行的分析，那么问题就转化成求每行最大得分和，对此我们可以用区间dp求解，
设dp[i][j]为i到j区间内最大得分he
推导可得转移方程：dp[i][j]=max(f[i-1][j]+a[i-1]p[k],f[i][j+1]+a[j+1]p[k]);

AC代码：

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
typedef __int128 ll;
int a[110][110];
ll dp[110][110];
ll po[85];
void init(){
      po[1]=2;
      for(int i=2;i<=80;i++)po[i]=po[i-1]*2;
}
inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
int main(){
    init();
     int n,m;
     ll sum=0;
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        scanf("%d",&a[i][j]);
     for(int coun=1;coun<=n;coun++){
        memset(dp,0,sizeof(dp));
        for(int d=1;d<=m;d++)
            for(int i=1,j=d;j<=m;j++,i++)
            dp[i][j]=max(dp[i+1][j]+a[coun][i]*po[m-d+1],dp[i][j-1]+a[coun][j]*po[m-d+1]);
        sum+=dp[1][m];
     }
     write(sum);
     return 0;
}