[每日一题] [NC16645] 矩阵取数游戏

题目大意：有一个矩阵，每行独立玩一个游戏，每次可以从头／尾取一个数并乘以2^i，希望总和最大。要求每行的总和最大值的和。矩阵很小(n,m <= 100)。

https://ac.nowcoder.com/acm/problem/16645

其实很简单，就是区间DP，每行单独做即可。考虑这一行第i到j个元素能组成的最大总和，那么dp[i, j] = max(2^1 * nums[i] + 2 * dp[i + 1, j], 2^1 * nums[j] + 2 * dp[i, j - 1])。

时间复杂度是O(r*c^2)。注意会爆long long，我用了__int128护体。

typedef __int128 ll;

int n, m;
#define MAXN 100
ll mat[MAXN][MAXN];
ll dorow(int r) {
  // dp[i][j] stores the maximum possible score choosing [i, j].
  VVL dp(m, VL(m, 0));
  for (int l = 1; l <= m; ++l) {
    for (int i = 0; i + l <= m; ++i) {
      int j = i + l - 1;
      if (l == 1) {
        dp[i][j] = mat[r][i] * 2;
        continue;
      }
      dp[i][j] = max(mat[r][i] * 2 + dp[i + 1][j] * 2, mat[r][j] * 2 + dp[i][j - 1] * 2);
    }
  }
  return dp[0][m - 1];
}
ll doit() {
  ll ans = 0;
  REP(r, n) {
    ans += dorow(r);
  }
  return ans;
}
int main(int argc, char* argv[]) {
  read(n, m);
  REP(i, n) {
    REP(j, m) {
      scanf("%lld", &mat[i][j]);
    }
  }
  ll ans = doit();
  kuaixie(ans);
  return 0;
}